Le PNG

Il y a quelques semaines, je me suis intéressé à un algorithme de compression d’image qui a révolutionné internet : le JPEG. Si le taux de compression est impressionnant et met en jeu des algorithmes géniaux et des biais de la vision humaine, il présente l’inconvénient de dégrader l’image et ne présente pas de canal alpha. 

Dégrader l’image, tout le monde connaît. L’absence de canal alpha, je vous dois quelques explications. Nous l’avons vu, un pixel est codé sur l’intensité des trois couleurs (rouge / vert / bleu). Le canal alpha est une nouvelle information qui identifie la transparence du pixel et permet d’indiquer la transparence de chaque pixel de l’image (RVBA).

L’intérêt est que si 2 images doivent se superposer, suivant la transparence de l’image du dessus, il sera possible de voir partiellement l’image au-dessous. C’est comme les panneaux sur les lieux touristiques où sont dessinés des scènes locales et les touristes se font prendre en photo en passant sa tête dans le trou (canal alpha à 0).  

C’est pour cela que 4 ans après le JPEG, un nouveau format apparaît, le Portable Network Graphics (PNG). Avec un nom pareil, Graphique portable sur le réseau (ou si on ne veut pas être trop littéral, image diffusable sur internet),  se positionne en concurrent en proposant de réhausser la qualité et l’usage au détriment du taux de compression. 

Comment fonctionne le PNG ? L’algorithme se décompose en trois étapes. Une étape de filtrage pour adapter les informations de l’image à un traitement de compression classique. Une étape de catalogage avec un algorithme proche du LZ77 vu précédemment, le LZSS. Une étape de codage entropique avec Huffman. 

Le filtrage 

Chaque pixel est codé en 3 sous-pixels rouge, vert et bleu (et un 4ème si la transparence est traitée). Classique. L’idée est de trouver une représentation de ce pixel différente pour que le catalogage lors de la deuxième étape soit le plus efficace. Pour cela, chaque pixel est calculé suivant la différence avec un pixel voisin. 5 stratégies possibles : 

• filtre None : on ne fait rien
• filtre Sub (soustraction) : le pixel est calculé par rapport au pixel à sa gauche 
• filtre Up (Haut) : le pixel est calculé par rapport au pixel au dessus 
• filtre Average (moyenne) : le pixel est calculé par rapport à la moyenne des pixels à gauche et au-dessus. 
• filtre Paeth : le choix du pixel de référence est réalisé suivant la plus faible distance. 

Pour chaque ligne de l’image, une stratégie sera choisie. Ainsi, la meilleure stratégie est gardée avant de passer à l’étape suivante. Le problème est de savoir quelle combinaison de stratégie sera la plus efficace. 5 stratégies pour une image de 400 lignes, 5⁴⁰⁰ ce n’est pas réalisable. Une approximation est donc utilisée même si elle n’assure pas la meilleure compression. 

Le catalogage – LZSS

LZSS est en référence à l’algorithme LZ77. Deux informaticiens, James A. Storer et Thomas Szimanski proposent une stratégie de catalogage dont le coût d’exécution sur les ordinateurs de l’époque (1982) reste raisonnable. 

Le catalogage consiste à enregistrer dans un registre les termes qui se répètent et à les identifier par un numéro qui les remplacera dans le texte original. Dans la proposition de Storer et Szimanski, le registre et le document final sont confondus. Si un doublon est identifié, il sera remplacé par la position et la longueur du terme identique trouvé.

Voici un lien vers une démonstration de l’algorithme. En anglais. Je n’ai pas trouvé mieux et la démonstration est très claire. 

L’encodage de Huffman

Comme toujours, il est utilisé en dernier pour chercher les derniers octets à compresser. La gestion de l’entropie semble être un domaine fantastique. Et l’algorithme proposé par Huffman en est le sommet. Cette étape réalisée, le fichier PNG est prêt à être diffusé sur les réseaux ou stocké dans les mémoires.

– 

Ou presque. Comme dans tout standard utilisé pour décrire et compresser des images, des données sont ajoutées pour le détailler un peu. 8 octets permettent de le reconnaître comme un fichier PNG. Un entête définit les caractéristiques du fichier. A la fin du fichier, des méta-données (position GPS, nom de l’appareil, …) peuvent être ajoutées. 

Le décodage et son affichage se font en sens inverse de l’algorithme d’encodage. Aucun calcul complexe n’est nécessaire, ce qui assure un décodage rapide. En tout cas plus rapide que le standard JPEG. Par contre, le taux de compression est entre 50% et 80%, soit une image dont la taille est au mieux divisée par 5, au pire par 2, …  

L’aspect réseau est à oublier sauf pour les photographes. De par son aspect sans perte, le PNG est principalement utilisé pour les captures d’écrans et la création de logos d’entreprises ou d’associations. Un format connu des spécialistes même s’il est intégré dans tous les équipements électroniques autour de nous. 

PNG et JPEG sont les algorithmes de compression d’images les plus populaires. Ils répondent à la majorité des besoins et sont bien connus de tous les équipements informatiques. Ils sont régulièrement mis à jour pour gagner en efficacité. 

Pourtant, il existe d’autres algorithmes de compression d’images. De grandes entreprises, comme Google avec le WebP, ou des ingénieurs inconnus comme Dominic Szablewski avec le QOI, proposent des alternatives crédibles à ces formats.  La concurrence en informatique a parfois du bon. 

Si vous avez un peu de temps, je vous conseille cette vidéo. Bien qu’en anglais, elle explique bien les stratégies autour du format PNG.