Jyrki Alakuijala, Ph.D., Google, Inc., 2023-03-09
Abstraite
WebP sans perte est un format d'image permettant de compresser des images ARVB sans perte. 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 des données séquentielle (LZ77), le codage de préfixe et un cache de couleurs sont utilisés pour la compression des données groupées. Des vitesses de décodage plus rapides que le format PNG ont été démontrées, ainsi qu'une compression plus dense de 25% que celle qui peut être obtenue avec le format PNG actuel.
1 Introduction
Ce document décrit la représentation sous forme compressée d'une image WebP sans perte. Il est conçu comme une référence détaillée pour la mise en œuvre d'un encodeur et d'un 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 supposer l'existence d'une fonction pour lire les 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 le moins significatif en commençant par les bits. Lorsque plusieurs bits sont lus en même temps, l'entier est construit à partir des données d'origine, dans l'ordre initial. Les bits les plus significatifs de l'entier renvoyé sont également les bits les plus significatifs des données d'origine. Ainsi, l'instruction
b = ReadBits(2);
est équivalente aux deux instructions ci-dessous:
b = ReadBits(1);
b |= ReadBits(1) << 1;
Nous supposons 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 ARVB 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 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. Une image WebP sans perte peut passer par quatre types de transformations différents avant d'être encodée en entropie. Les informations de transformation du flux de bits contiennent les données requises pour appliquer les transformations inverses respectives.
2 Nomenclature
- ARVB
- Valeur de pixel composée des valeurs alpha, rouge, vert et bleu.
- Image ARVB
- Tableau bidimensionnel contenant des pixels ARVB.
- cache de couleurs
- Petit tableau orienté par hachage permettant de 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ée à l'aide d'un petit entier (jusqu'à 256 dans le format sans perte WebP).
- image de transformation de couleur
- Image de sous-résolution en deux dimensions contenant des données sur les corrélations de composants de couleur.
- cartographie des distances
- Modifie les distances LZ77 pour avoir les valeurs de pixels les plus faibles dans la proximité bidimensionnelle.
- image d'entropie
- Image de sous-résolution en deux dimensions indiquant le codage d'entropie à utiliser dans un carré respectif de l'image, c'est-à-dire que chaque pixel est un méta code de préfixe.
- LZ77
- Algorithme de compression à fenêtre glissante basé sur un dictionnaire qui émet des symboles ou les décrit comme des séquences d'anciens symboles.
- code méta-préfixe
- Petit entier (jusqu'à 16 bits) qui indexe un élément dans la table de méta-préfixes.
- image prédicteur
- Image de sous-résolution en deux dimensions indiquant le prédicteur spatial utilisé pour un carré particulier de l'image.
- code de préfixe
- Méthode classique de codage entropie où un plus petit nombre de bits est utilisé pour des codes plus fréquents.
- codage des préfixes
- Moyen d'entropie le code d'entiers plus grands, qui code quelques bits de l'entropie à l'aide d'un code d'entropie 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 large.
- commande de ligne de numérisation
- Ordre de traitement des pixels (de gauche à droite et de haut en bas), à partir du pixel supérieur gauche. Une fois la ligne terminée, continuez à partir de la colonne de gauche de la ligne suivante.
3 En-tête RIFF
Le conteneur RIFF se trouve au début de l'en-tête. Elle se compose des 21 octets suivants:
- Chaîne "RIFF".
- Valeur de 32 bits de la longueur du fragment, qui correspond à la taille totale du fragment contrôlée par l'en-tête RIFF. Normalement, cela correspond à la taille de la charge utile (taille du fichier moins 8 octets: 4 octets pour l'identifiant "RIFF" et 4 octets pour le stockage de la valeur elle-même).
- Chaîne "WEBP" (nom du conteneur RIFF).
- Chaîne "VP8L" (FourCC pour les données d'image encodées sans perte).
- Valeur petit-endian de 32 bits du nombre d'octets dans le flux sans perte.
- Signature d'un 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 sous la forme d'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 à 16 384 × 16 384 pixels.
Le bit alpha_is_used est un indice et ne devrait pas avoir d'incidence sur le décodage. Elle doit être définie sur 0 lorsque toutes les valeurs alpha sont égales à 255 dans l'image, et sur 1 dans le cas contraire.
int alpha_is_used = ReadBits(1);
Le numéro de version 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 couleurs. Elles peuvent rendre la compression finale plus dense.
Une image peut subir quatre types de transformation. 1 bit 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 prédicteur) ne comportent aucune transformation, pas même le 0 bit 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. En outre, les données de transformation peuvent être choisies 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. Les données de transformation contiennent les informations requises pour appliquer la transformation inverse et dépendent du type de transformation. Les transformations inverses sont appliquées dans l'ordre inverse dans lequel elles sont lues à partir du flux de bits, c'est-à-dire la dernière en premier.
Nous allons ensuite décrire les données de transformation pour différents types.
4.1 Transformation du prédicteur
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 de la ligne d'analyse), et seule la valeur résiduelle (réelle – prévue) est encodée. Le composant vert d'un pixel définit lequel des 14 prédicteurs est utilisé dans un bloc particulier de l'image ARVB. 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 ARVB. Cette image de sous-résolution est encodée selon les techniques décrites dans le chapitre 5.
Le nombre de colonnes de bloc, transform_width, est utilisé dans l'indexation bidimensionnelle. Pour un pixel (x, y), on peut calculer l'adresse du bloc de filtre correspondant 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 de pixel actuelle 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 supérieur gauche, T signifie haut, TR signifie haut à droite et 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à été traités, et le pixel P et les X pixels sont inconnus.
Compte tenu des pixels voisins précédents, les différents modes de prédiction sont définis comme suit.
| Mode | Valeur prédite de chaque canal du pixel actuel |
|---|---|
| 0 | 0xff000000 (correspond à une 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 | Select(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 Select 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);
}
Certains pixels de bordure font l'objet de règles de traitement spéciales. S'il y a une transformation de prédiction, quel que soit le mode [0..13] pour ces pixels, la valeur prédite pour le pixel le plus à gauche de l'image est 0xff000000. Tous les pixels de la ligne supérieure sont des pixels en L et tous les pixels de la colonne la plus à gauche sont des pixels en T.
Le ciblage du pixel TR pour les pixels dans 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 figurent pas sur la bordure, mais que le pixel le plus à gauche sur la même ligne que le pixel actuel est utilisé en tant que 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 de couleur est de décorérer les valeurs R, V et B de chaque pixel. La transformation de couleur conserve la valeur du vert (G) telle quelle, transforme la valeur du rouge (R) en fonction de la valeur du vert et transforme la valeur du bleu (B) en fonction de la valeur du vert, puis du rouge.
Comme pour la transformation du prédicteur, l'image est d'abord divisée en blocs, puis 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 de couleur.
typedef struct {
uint8 green_to_red;
uint8 green_to_blue;
uint8 red_to_blue;
} ColorTransformElement;
La transformation de couleur réelle est effectuée en définissant un delta de transformation de couleur. Le delta de transformation des couleurs dépend de ColorTransformElement, qui est le même pour tous les pixels d'un bloc particulier. Le delta est soustrait lors de la transformation de la couleur. La transformation de couleur inverse se contente d'ajouter ces deltas.
La fonction de transformation de couleur 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 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) en représentation signée de 8 bits (int8) est nécessaire avant d'appeler ColorTransformDelta(). La valeur signée doit être interprétée comme un nombre de complément à deux de 8 bits (c'est-à-dire que la plage uint8 [128..255] est mappée sur la plage [-128..-1] de sa valeur convertie en int8).
La multiplication doit être effectuée avec plus de précision (au moins 16 bits). La propriété de l'extension de signe de l'opération de décalage n'a pas d'importance ici. Seuls les 8 bits les plus bas sont utilisés à partir du résultat, et le décalage d'extension de signe et le décalage non signé sont cohérents.
Nous décrivons maintenant le contenu des données de transformation de couleur afin que le décodage puisse appliquer la transformation de couleur inverse et récupérer les valeurs d'origine rouge et bleue. Les trois premiers bits des données de transformation de couleur 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 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 cte.green_to_blue et le composant bleu 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. Comme indiqué 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 Soustraire la transformation verte
La transformation "soustraction verte" soustrait les valeurs vertes des valeurs rouge et bleue de chaque pixel. Lorsque cette transformation est présente, le décodeur doit ajouter la valeur du vert 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, mais comme il n'y a pas de données supplémentaires ici, la transformation "soustraction verte" peut être codée en utilisant moins de bits qu'une transformation de couleur complète.
4.4 Transformation d'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'indices de couleur et de remplacer les valeurs de pixels par les index du tableau. C'est ce que permet la transformation d'indexation des couleurs. (Dans le contexte de l'encodage sans perte WebP, nous n'appelons pas cela une transformation par palette, car un concept similaire, mais plus 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 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 des pixels par l'indice correspondant: le canal vert des pixels est remplacé par l'index, toutes les valeurs alpha sont définies sur 255, et toutes les valeurs en rouge et bleu sur 0.
Les données de transformation contiennent la taille de la table de couleurs et les entrées qu'elle contient. 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 en utilisant le 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 de l'image ni les transformations, en supposant que la hauteur est de 1 pixel et la 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 une entropie beaucoup plus faible que les couleurs elles-mêmes, ce qui permet de réaliser des économies considérables pour des images plus petites. Lors du décodage, vous pouvez obtenir chaque couleur finale de la table de couleurs en ajoutant les valeurs de composant de couleur précédentes 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 en pixels (qui sont des indices 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 la 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 pixel. Le regroupement de pixels regroupe plusieurs (2, 4 ou 8) pixels en un seul pixel, ce qui réduit la largeur de l'image respectivement. Le regroupement de pixels permet un codage entropique de distribution conjointe plus efficace des pixels voisins et offre des avantages de type arithmétique au code d'entropie, mais il ne peut être utilisé que s'il n'y a pas plus de 16 valeurs uniques.
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 la valeur 0, 1, 2 ou 3. La valeur 0 indique qu'aucun regroupement de pixels n'est nécessaire pour l'image. La valeur 1 indique que deux pixels sont combinés et que chaque pixel présente une plage de [0...15]. La valeur 2 indique que quatre pixels sont combinés et que chaque pixel présente une plage de [0..3]. La valeur 3 indique que huit pixels sont combinés et que chaque pixel est associé à 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 au niveau de x est placée dans les 4 bits les moins significatifs de la valeur du vert en x / 2, et une valeur en vert à x + 1 est positionnée dans les 4 bits les plus significatifs de la valeur verte à x / 2.width_bits= 2: pour chaque valeur x, où x ≡ 0 (mod 4), une valeur verte au niveau de x est placée dans les 2 bits les moins significatifs de la valeur verte en x / 4, et les valeurs vertes entre x + 1 et x + 3 sont positionnées dans l'ordre des bits les plus significatifs de la valeur verte en fonction de x / 4.width_bits= 3: pour chaque valeur x, où x ≡ 0 (mod 8), une valeur verte au niveau de x est positionnée dans le bit le moins significatif de la valeur du vert en x / 8, et les valeurs des verts à x + 1 à x + 7 sont positionnées dans l'ordre des bits les plus significatifs de la valeur des verts en x / 8.
Après lecture de 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 de la ligne d'analyse.
5.1 Rôles des données d'image
Nous utilisons les données d'image dans cinq rôles différents:
- Image ARVB: stocke les pixels réels de l'image.
- Image d'entropie: stocke les méta-codes de préfixe (voir Décoder les codes de préfixe Meta).
- Image du prédicteur: stocke les métadonnées pour la transformation du prédicteur (consultez la section Transformation du prédicteur).
- Image de transformation de couleur: créée par les valeurs
ColorTransformElement(définies dans "Color Transform") pour différents blocs de l'image. - Image d'indexation des couleurs: tableau de taille
color_table_size(jusqu'à 256 valeurs ARVB) qui stocke les métadonnées pour 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 leur rôle.
L'image est d'abord divisée en un ensemble de blocs de taille fixe (généralement 16 x 16). Chacun de ces blocs est modélisé à l'aide de ses propres codes d'entropie. En outre, 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 vous permet de ne stocker ce code qu'une seule fois. Par exemple, un encodeur peut trouver des blocs similaires en les regroupant selon leurs propriétés statistiques ou en joignant de manière répétée une paire de clusters sélectionnés de manière aléatoire, lorsqu'il réduit le nombre total de bits nécessaires pour encoder l'image.
Chaque pixel est encodé selon l'une des trois méthodes possibles:
- Littéraux codés par préfixe: chaque canal (vert, rouge, bleu et alpha) est codé par entropie indépendamment.
- LZ77 référence arrière: séquence de pixels copiée ailleurs dans l'image.
- Code de cache de couleurs: utilise un court code de hachage multiplicatif (index de cache de couleurs) d'une couleur récemment observée.
Les sous-sections suivantes décrivent chacune de ces options en détail.
5.2.1 Littéraux codés en préfixe
Le pixel est stocké sous forme de valeurs codées en préfixe 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 LZ77
Les références inverses sont des tuples de longueur et de code de distance:
- La longueur indique le nombre de pixels dans l'ordre des lignes de recherche qui doivent être copiés.
- Le code de distance est un nombre indiquant la position d'un pixel vu précédemment, à 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 sous codage avec préfixe LZ77.
Le codage de préfixe LZ77 divise les grands nombres entiers 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).
Logique: Cette approche réduit le besoin de stockage pour le code d'entropie. De plus, les valeurs élevées sont généralement rares. Par conséquent, des bits supplémentaires peuvent être utilisés pour très peu de valeurs dans l'image. Ainsi, cette approche se traduit par une meilleure compression dans l'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 de préfixe | Infos 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 de préfixe se présente comme 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 précédemment détecté, à 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 recherche, avec un décalage de 120.
Les plus petits codes de distance [1..120] sont spéciaux et sont réservés à un voisinage proche du pixel actuel. Ce quartier comprend 120 pixels:
- Pixels compris entre une et sept lignes au-dessus du pixel actuel, et jusqu'à huit colonnes à gauche ou sept colonnes à droite du pixel actuel. [Total de ces pixels =
7 * (8 + 1 + 7) = 112]. - Pixels situés sur la même ligne que le pixel actuel et comportant jusqu'à huit colonnes à gauche du pixel actuel. [
8ces pixels].
Le mappage entre le code de distance distance_code et le décalage de pixels 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 différence de 1 pixel dans la direction Y).
De même, le code de distance 3 indique le pixel supérieur gauche.
Le décodeur peut convertir un code de distance distance_code en une distance de l'ordre des lignes de recherche 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 indiqué 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:De cette façon, les couleurs récemment utilisées peuvent parfois être référencées plus efficacement que de les émettre à l'aide des deux autres méthodes (décrites aux 5.2.1 et 5.2.2).
Les codes des caches de couleurs 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 égal à 0, aucun code de cache de couleurs n'existe et ils ne sont pas 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 de 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 ARVB. 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 de conflit.
Au début du décodage ou de l'encodage d'une image, toutes les entrées de toutes les valeurs de cache de couleurs sont définies sur zéro. Le code du cache de couleurs est converti dans 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 un référencement rétro ou sous forme de 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 réels.
En particulier, le format utilise un codage de préfixe à variante spatiale. En d'autres termes, différents blocs de l'image peuvent éventuellement utiliser différents codes d'entropie.
Logique: Certaines zones de l'image peuvent avoir des caractéristiques différentes. Ainsi, leur permettre d'utiliser différents codes d'entropie offre plus de flexibilité et une meilleure compression potentiellement.
6.2 Détails
Les données d'image encodées se composent de plusieurs parties:
- Décoder et créer les codes de préfixe
- Codes de préfixe Meta.
- Données d'image codées par entropie.
Un ensemble de cinq codes de préfixe est associé à chaque pixel (x, y) donné. Ces codes sont les suivants (par ordre de flux de bits):
- Code de préfixe n° 1: utilisé pour le canal vert, la longueur de la référence arrière et le cache de couleurs.
- Code de préfixe n° 2, n° 3 et n° 4: utilisé respectivement pour les canaux rouge, bleu et alpha.
- Code de préfixe n° 5: utilisé pour la distance de référence arrière.
À partir de maintenant, nous appellerons cet ensemble un groupe de codes de préfixe.
6.2.1 Décoder et construire les 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 égal à 1, il s'agit d'un code simple avec une longueur de code.
- Si ce bit a la valeur 0, il s'agit d'un code de longueur de code normale.
Dans les deux cas, des longueurs de code inutilisées peuvent faire partie du flux. Cela peut être inefficace, mais le format le permet. L'arborescence décrite doit être une arborescence binaire complète. Un nœud feuille unique est considéré comme une arborescence binaire complète et peut être encodé à l'aide du code simple ou du code de longueur de code normale. Lors du codage d'un nœud feuille unique à l'aide du code de longueur de code normale, toutes les longueurs de code sauf un sont des zéros, et la valeur du nœud feuille unique est marquée avec la longueur 1, même si aucun bit n'est consommé lorsque cette arborescence à nœud feuille unique est utilisée.
Code de longueur de code simple
Cette variante est utilisée dans le cas particulier où seuls un ou deux symboles de préfixe sont compris dans la plage [0..255] avec une longueur de code 1. Toutes les autres longueurs de code de préfixe sont implicitement des zéros.
Le premier bit indique le nombre de symboles:
int num_symbols = ReadBits(1) + 1;
Voici les valeurs des symboles.
Ce premier symbole est codé en 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 symbole, s'il est présent, est toujours considéré comme compris dans la plage [0...255] et est codé avec 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 : Autre cas particulier : toutes les longueurs de code de préfixe sont des zéros (un code de préfixe vide). Par exemple, un code de préfixe de distance peut être vide s'il n'y a pas de références arrière. De même, les codes de préfixe alpha, rouge et bleu peuvent être vides si tous les pixels au sein du même méta-code de préfixe sont produits à l'aide du cache de couleurs. Cependant, ce cas ne nécessite aucune manipulation particulière, car les codes de préfixe vides peuvent être codés comme ceux contenant un seul symbole 0.
Longueur de code normale
Les longueurs du code de préfixe sont de 8 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. Les longueurs de code de niveau inférieur, code_length_code_lengths, doivent d'abord être lues. Les autres 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 sa 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 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 des longueurs de code maximales de max_symbol.
- Le code [0..15] indique des 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, soit
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], soit
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) 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 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'arborescence à nœud feuille unique, dans laquelle la valeur du nœud feuille est marquée avec la valeur 1 et les autres valeurs par 0.
6.2.2 Décodage des codes de préfixe Meta
Comme indiqué précédemment, ce 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 identifiant 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 en tant que rôle d'une image ARVB.
Les codes de méta-préfixe peuvent être de deux façons, indiquées par une valeur de 1 bit:
- Si ce bit est égal à zéro, un seul code méta-préfixe est utilisé partout dans l'image. Aucune autre donnée n'est stockée.
- Si ce bit est égal à un, l'image utilise plusieurs codes méta-préfixes. Ces méta-codes de préfixes 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 méta-préfixe 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 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 précédemment.
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
Pour obtenir le nombre de groupes de codes de préfixe dans l'image ARVB, recherchez le plus grand méta-préfixe à partir 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 l'image d'entropie.
Étant donné que 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;
À partir d'un pixel (x, y) dans l'image ARVB, 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. En outre, 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 la section Décoder les données d'images codées par entropie.
6.2.3 Décoder les données d'images 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 section précédente). 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 correspond à n'importe quel entier compris entre 0 et (256 + 24 + color_cache_size- 1).
L'interprétation de "S" dépend de sa valeur:
- Si S < 256
- Utilisez "S" comme composant vert.
- Lisez en rouge à partir du flux de bits à l'aide du code de préfixe 2.
- Lisez en bleu le flux de bits à l'aide du code de préfixe #3.
- Lisez la valeur alpha à partir du flux de bits à l'aide du code de préfixe #4.
- Si S >= 256 et S < 256 + 24
- Utilisez S - 256 comme préfixe de longueur.
- Lire les bits supplémentaires pour la longueur à partir du flux de bits.
- Déterminez la longueur L de la référence arrière à partir du code de préfixe de longueur et des bits supplémentaires lus.
- Lisez le code du préfixe de distance à partir du flux de bits à l'aide du code de préfixe #5.
- Lire les bits supplémentaires pour la distance par rapport au flux de bits.
- Déterminer la distance D de la référence arrière, à partir du code du préfixe de distance et des bits supplémentaires lus.
- Copiez L pixels (dans l'ordre des lignes de recherche) à partir de la séquence de pixels à partir de la position actuelle, moins D pixels.
- Si S >= 256 + 24
- Utilisez S - (256 + 24) comme index dans le cache de couleurs.
- Récupérez la couleur ARVB à partir du cache de couleurs de cet index.
7 Structure globale du format
Vous trouverez ci-dessous une vue au format ABNF (Augmented Backus-Naur Form) RFC 5234 RFC 7405. Il ne couvre pas tous les détails. La fin de l'image (EOI) est implicitement codée en 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