RFC: 2083
Statut : Proposition
Retour à l'index des normes : INDEX FRANCAIS
Ce chapitre décrit les algorithmes de filtrage utilisés avant la compression de l'image. Le but de ce filtrage est de préparer l'image en vue d'une compression optimale.
La méthode de filtrage 0 de la spécification PNG définit cinq types de filtres de base :
| Type | Nom |
| 0 | Aucun |
| 1 | Différentiel horizontal |
| 2 | Différentiel vertical |
| 3 | Prédictif par Moyenne |
| 4 | Filtre de Paeth |
(Notez que cette méthode 0 spécifiée dans le bloc IHDR définit précisément cet ensemble de cinq filtres. Si dans le futur cet ensemble doit être complété, il faudra prendre un nouveau numéro de méthode, de sorte qu'un décodeur n'aura pas à attendre la décompression des données pour découvrir que d'autres filtres ont été utilisés).
L'encodeur peut choisir lequel de ces cinq filtres appliquer à chacune des lignes de l'image, et ce ligne par ligne. Les lignes d'images filtrées seront précédées du numéro de filtre utilisé, avant d'être soumises à l'étage de compression.
Les algorithmes de filtrage prennent en compte les octets, et non les pixels, quelque soit la profondeur de bit du pixel ou le modèle de couleur de l'image. Les algorithmes de filtrage s'intéressent à la séquence d'octets constituée par une ligne d'image, telle que spécifiée par le chapitre Codage de l'image (Section 2.3). Si l'image contient un canal alpha, celui-ci est filtré au même titre que les autres échantillons.
Lorsque l'image est entrelacée, chaque passe d'entrelacement est traité par le filtre comme une image indépendante. Le filtre s'intéressera alors à la séquence d'octets formée par les informations des pixels transmis pendant la passe d'entrelacement, la "ligne précédente" étant celle précédemment transmise dans la même passe, et non la ligne adjacente dans l'image originale. Notez que la "sous-image" transmise dans une passe reste rectangulaire, mais de largeur et de hauteur inférieure à celle de l'image complète. Le filtrage n'est pas appliqué lorsque la sous-image est vide.
Pour tous les filtres, les octets "à gauche du" premier octet d'une ligne doivent être considérés comme étant à zéro. Pour les filtres qui prennent en compte la ligne "précédente", on prendra pour ligne précédente à la première ligne d'une passe (ou la première ligne d'image si celle-ci n'est pas entrelacée) une ligne fictive d'octets tous nuls.
Pour inverser l'effet d'un filtre, le décodeur devra utiliser les valeurs décodées du pixel précédent sur la même ligne, ou du pixel immédiatement au dessus (en même position dans la ligne précédente), ainsi que du pixel précédent ce dernier. Cela implique que le décodeur ait la capacité de stocker en mémoire au moins une ligne complète. Même pour les filtres qui ne se réfèrent pas à la ligne antérieure, le décodeur devra être en mesure de mémoriser la ligne courante, dans la mesure où rien empêche que le filtre utilisé à ligne suivante n'ait pas à son tour à se référer à cette ligne.
PNG n'impose aucune restriction sur le type de filtre à utiliser sur une ligne d'image. Cependant, les divers filtres n'ont pas tous la même efficacité selon le type de données. Cf. Recommandations pour les Encodeurs: Sélection du filtre (Section 9.6).Cf. Motivations: Filtrage (Section 12.9).
Le filtre de type 0 est un "passe tout". Les données ne sont pas modifiées. Sa présence répond seulement à l'obligation d'ajouter un octet de type de filtre en tête de ligne.
Le filtre dit "différentiel horizontal" ou "Sub" code la différence entre l'octet d'un pixel et l'octet correspondant du pixel précédent sur la même ligne.
Pour calculer chaque pixel, il suffit d'appliquer la formule suivante à chaque pixel de la ligne :
Sub(x) = Raw(x) - Raw(x-bpp)où x varie de zéro jusqu'au nombre de pixels dans la ligne moins 1, Raw(x) est la valeur de l'octet à la position x dans la ligne, et bpp représente le nombre d'octets nécessaire au codage d'un pixel (un au minimum). Par exemple, pour le modèle de couleur 2 avec une profondeur de bits de 16, bpp vaut 6 (trois échantillons, 2 octets par échantillon); pour le modèle 0 avec une profondeur de bit de 2, bpp vaut 1 (arrondi); pour le modèle 4 avec une profondeur de bits de 16, bpp vaut 4 (deux octets de niveau de gris plus deux octets du canal alpha).
Notez que ce calcul est fait pour chaque octet, indépendamment de la profondeur de bits. Dans une image 16 bits, chaque MSB est "prédit" à partir du MSB précédent, et chaque LSB à partir du LSB précédent, grâce à la définition de bpp.
L'arithmétique utilisée est non signée modulo 256, de sorte que l'entrée et la sortie restent dans le codage admissible d'un seul octet. La séquence des valeurs Sub(x) correspond à la ligne filtrée.
Pour tout x < 0, on suppose Raw(x) = 0.
Pour inverser l'effet de ce filtre, il suffit de partir de 0, et d'ajouter arithmétiquement la valeur Sub(x) :
Raw(x) = Sub(x) + Raw(x-bpp)(modulo 256), Raw(x-bpp) étant le précédent octet déjà décodé.
Le filtre "différentiel vertical", ou "Up" fonctionne sur le même principe que le différentiel horizontal, sauf que le "prédicteur" utilisé est le pixel situé juste au dessus, plutôt que le précédent sur la même ligne. Pour calculer ce filtre, la formule à appliquer devient :
Upn(x) = Rawn(x) - Rawn-1(x)où x varie de zéro jusqu'au nombre de pixels dans la ligne moins 1, Rawn(x) est la valeur de l'octet à la position x dans la ligne traitée (ligne n), et Rawn-1(x) la valeur de l'octet de même position dans la ligne au dessus (précédente).
Ce calcul est fait octet par octet, indépendamment de la profondeur bit. L'arithmétique utilisée est non signée modulo 256, de sorte que l'entrée et la sortie restent dans le codage admissible d'un seul octet. La séquence des valeurs Up(x) correspond à la ligne filtrée. Pour la première ligne de l'image (ou de la passe dans le cas d'une image entrelacée), On supposera que tous les Rawn-1(x) = 0 quelque soit x.
Pour inverser l'effet du filtre, on appliquera la formule suivante :
Rawn(x) = Rawn-1(x) + Upn(x)(modulo 256), Rawn-1(x) étant l'octet déjà décodé de la ligne précédente.
Le filtre différentiel "par moyenne" (Average) exploite la moyenne arithmétique des deux prédicteurs précédents (pixel précédent sur la même ligne, même pixel sur la ligne précédente) comme base du codage du pixel.
Pour calculer ce filtre, la formule à appliquer devient :
Averagen(x) = Rawn(x) - floor((Rawn(x-bpp)+Rawn-1(x))/2)où x est la position du pixel à traiter (de 0 à largeur -1), et bpp le nombre d'octets par pixel tel que défini pour le filtre 1.
Ce calcul est fait octet par octet, indépendamment de la profondeur bit. La séquence des valeurs Averagen(x) correspond à la ligne filtrée. La soustraction de la moyenne (prédicteur) à la valeur de l'échantillon est faite modulo 256 de sorte à ce que les valeurs de départ et d'arrivée soient codables dans un octet. Par contre, la somme Rawn(x-bpp)+Rawn-1(x) doit être exacte et sans dépassement de capacité (selon une arithmétique à au moins 9 bits). La fonction floor() arrondit le résultat de la division au premier entier inférieur, si celui-ci n'est pas entier; il s'agira donc d'une division entière, assimilable à un décalage d'un bit vers la droite.
Pour tout x < 0, on supposera que Rawn(x) = 0. Pour la première ligne (ou la première ligne d'une passe si l'image est entrelacée), on considérera la présence d'une ligne fictive Raw0(x) = 0 quelque soit x.
Pour inverser l'effet du filtre, on utilisera la formule suivante :
Rawn(w) = Averagen(x) + floor((Rawn(x-bpp)+Rawn-1(x))/2)dans laquelle le résultat est calculé modulo 256, et Rawj(x) correspond à une valeur déjà extraite.
Le filtre de Paeth calcule une fonction prédictive se basant sur les trois pixels voisins (gauche, au-dessus, au dessus à gauche), et choisit comme prédicteur la valeur du pixel la plus proche de celle du pixel à traiter. Cette technique a été instaurée par Alan W. Paeth [PAETH]. Pour calculer ce filtre, appliquer la formule suivante à tous les octets de la ligne :
Paethn(x) = Rawn(x) - PaethPredictor(Rawn(x-bpp), Rawn-1(x), Rawn-1(x-bpp))où x est la position du pixel à traiter (de 0 à largeur -1), et bpp le nombre d'octets par pixel tel que défini pour le filtre 1.
Ce calcul est fait octet par octet, indépendamment de la profondeur bit. L'arithmétique utilisée est non signée modulo 256, de sorte que l'entrée et la sortie restent dans le codage admissible d'un seul octet. La séquence des valeurs Paethn(x) correspond à la ligne filtrée. Le prédicteur de Paeth est défini par le pseudo-code suivant ::
function PaethPredictor (a, b, c)
begin
; a = left, b = above, c = upper left
p := a + b - c ; initial estimate
pa := abs(p - a) ; distances to a, b, c
pb := abs(p - b)
pc := abs(p - c)
; return nearest of a,b,c,
; breaking ties in order a,b,c.
if pa <= pb AND pa <= pc then return a
else if pb <= pc then return b
else return c
end
Les calculs dans le prédicteur de Paeth doivent être exécutés sans dépassement de capacité. L'arithmétique modulo 256 ne sera utilisée que dans l'étape finale de soustraction du prédicteur à la valeur non filtrée de l'octet.
Notez que l'ordre dans lequel les pixels prédicteurs sont testés est important et ne doit pas être altéré. L'ordre impératif est: le pixel de gauche, le pixel au dessus, et le pixel au dessus à gauche. (Cet ordre est différent de celui donné dans l'article de Paeth).
Pour tout x < 0, on supposera que Rawn(x) = 0. Pour la première ligne (ou la première ligne d'une passe si l'image est entrelacée), on considérera la présence d'une ligne fictive Raw0(x) = 0 quelque soit x. Pour inverser l'effet du filtre, on utilisera la formule suivante :
Rawn(x) = Paethn(x) + PaethPredictor(Rawn(x-bpp), Rawn-1(x), Rawn-1(x-bpp))dans laquelle le résultat est calculé modulo 256, et Rawj(x) correspond à une valeur déjà extraite.