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. Des vitesses de décodage plus rapides que le 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 de l'implémentation de l'encodeur et du décodeur sans perte WebP.
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 qui les contient, et les bits de chaque octet sont lus dans l'ordre du bit le moins significatif en premier. 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);
est équivalent aux deux énoncés ci-dessous :
b = ReadBits(1);
b |= ReadBits(1) << 1;
Nous supposons que chaque composant de couleur, à savoir l'alpha, le rouge, le bleu et le vert, est représenté à l'aide d'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 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ée à l'aide d'un petit entier (jusqu'à 256 dans WebP sans perte).
- image de transformation des couleurs
- Image bidimensionnelle à résolution inférieure contenant des données sur les corrélations des composants de 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 entropie dans laquelle un nombre plus faible de bits est utilisé pour les codes plus fréquents.
- codage de préfixe
- Méthode permettant d'encoder en entropie des entiers plus grands, qui code 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.
3 En-tête RIFF
Le début de l'en-tête contient le conteneur RIFF. Il s'agit des les 21 octets suivants:
- Chaîne "RIFF".
- 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).
- Chaîne 'WEBP' (nom du conteneur RIFF).
- Chaîne "VP8L" (code FourCC pour les données d'image encodées sans perte).
- Valeur de 32 bits en ordre little-endian du nombre d'octets dans le flux sans perte.
- 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 en tant qu'entiers 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);
Le numéro de version est un code de trois 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 prédictive
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 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
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, la 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éfinis 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élérer les valeurs R, G 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 de couleur.
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 bas sont utilisés à partir du résultat et dans ces bits, le le changement d'extension de 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 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, des instances ColorTransformElement des blocs sont décodées et la transformation de couleur inverse est appliquée aux valeurs ARGB des pixels. En tant que
mentionné précédemment, cette transformation de couleur
inverse consiste simplement à ajouter
ColorTransformElement aux canaux rouge et bleu. Les canaux alpha et vert 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 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, 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 pixel uniques, il peut être plus efficace de créer un tableau d'indices de couleur et de remplacer les valeurs de pixel par les indices 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 seuil (256), un tableau de ces valeurs ARGB est créé, qui est ensuite utilisé pour remplacer les valeurs de pixel 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 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. La table de couleurs peut être obtenue en lisant une image, sans l'en-tête RIFF, la taille de l'image et les transformations, en supposant une hauteur de 1 pixel et une largeur 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 elles-mêmes, ce qui permet de réaliser des économies importantes pour les images plus petites. 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 du 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:
- Image ARGB : stocke les pixels réels de l'image.
- Image d'entropie: stocke les codes de préfixe Meta (voir "Decoding of Meta Prefix Codes" (Décodage des codes de préfixe Meta).
- Image du prédicteur: stocke les métadonnées pour la transformation du prédicteur (voir Transformation du prédicteur).
- Image de transformation de couleur : créée à l'aide de valeurs
ColorTransformElement(définies dans "Transformation de couleur") pour différents blocs de l'image. - 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'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 minimisé si des blocs statistiquement similaires partagent un code d'entropie, ce qui ne le stocke qu'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:
- Littéraux codés en préfixe: chaque canal (vert, rouge, bleu et alpha) est de manière indépendante.
- Référence arrière LZ77: séquence de pixels copiée ailleurs dans l'image.
- 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 balayage.
- 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 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 nécessaire 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 voisinage est composé de 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. [
8de 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 correspond à la mise en correspondance indiquée 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.
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 du cache de couleur est converti en cette couleur au moment du 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 suit : 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:
- Décoder et construire les codes de préfixe.
- Codes de préfixe Meta.
- Données d'image encodées en 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.
- 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.
Dorénavant, nous appellerons cet ensemble un groupe de codes de préfixe.
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 symboles de préfixe se trouvent dans la plage [0..255] avec une longueur de code 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 des symboles.
Ce premier symbole est codé sur 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. 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 avec longueur de code 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 ; 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 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 précédente valeur non nulle [3..6], c'est-à-dire
3 + ReadBits(2)fois. Si le code 16 est utilisé avant qu'une valeur non nulle n'ait été émise, une valeur de 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é à l'aide de leurs tailles d'alphabet 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 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 à 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 méta, indiquées par une valeur de 1 bit :
- Si ce bit est nul, un seul code de préfixe méta est 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 de métadonnées
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.
É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;
É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];
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:
- Si S < 256
- Utilisez le S comme composant vert.
- Lisez le rouge à partir du flux de bits à l'aide du code de préfixe 2.
- Lisez le bleu du flux de bits à l'aide du code de préfixe 3.
- Lisez la version alpha du flux de bits à l'aide du code de préfixe n° 4.
- Si S >= 256 & D < 256 + 24
- Utilisez S-256 comme préfixe de longueur.
- Lire les bits supplémentaires pour la longueur du flux de bits.
- 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.
- Lisez le code du préfixe de distance du flux de bits à l'aide du code de préfixe #5.
- Lire des bits supplémentaires pour la distance à partir du flux de bits.
- 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.
- 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.
- Si S >= 256 + 24
- Utilisez S - (256 + 24) comme index dans le cache de couleurs.
- 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 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