Peut-être avez-vous déjà un jour généré une image similaire à celle-ci pour pouvoir afficher (en utilisant le principe de sprite CSS) un système de notation en étoiles allant de zéro à cinq avec les demis.

Fichier PNG de 6475 octets.

Et puis en réflechissant un peu vous vous êtes dit qu’on pouvait éventuellement réduire le tout à juste une étoile vide, une étoile pleine et une étoile moit moit. Comme vous êtes consciencieux vous avez optimisé l’image obtenue avec ImageOptim.

Fichier PNG de 3623 octets.

Super, votre boss vous félicite pour votre ingéniosité et votre contribution à l’amélioration les perfs du site.
Mais la nuit suivante dans un songe Jim Morrison et un indien zarbi à moitié à poil vous suggèrent de placer les étoiles à la verticale. Coool…

Fichier PNG de 3580 octets.

Diantre Jim Morrison avait raison, le fichier est légèrement plus petit !
Piqué par la curiosité vous vous lancez dans la permutation des étoiles, 3! ça fait 6 images différentes par axe donc un total de 12 images.


Vous optimisez soigneusement le tout avec ImageOptim…

…et même avec CryoPNG qui est lent comme un veau.

Avec à chaque fois un résultat similaire : le fichier à la verticale avec les étoiles dans l’ordre : vide, pleine et moit moit est bien le plus petit, il y a même un petit gain de 50 octets avec CryoPNG. Sans trop comprendre pourquoi vous remerciez toutefois Jim Morrison et vous vous demandez s’il aurait officié en tant que dev front à notre époque.

Fichier PNG de 3530 octets.

Tout va bien jusqu’au moment où vous avez raconté votre histoire à Sergey qui a voulu reproduire votre expérence et qui tout fièrement vous rapporte un fichier plus petit… avec les étoiles sur l’axe horizontal. En fait ce bougre s’est contenté d’optimiser vos fichiers avec ScriptPNG sur Windows.



Fichier PNG de 3516 octets.

Une chose est certaine le cofondateur de The Doors n’a jamais utilisé Windows, mais comment expliquer les variations de taille des fichiers pour un contenu identique mais disposé différement ?

C’est à la fois simple et compliqué car trois mécanismes différents interviennent ici : la distance entre les éléments similaires au sein de l’image, l’ordre de la palette et l’efficacité du découpage en blocks du flux compressé ; dans cet exemple on évite toutefois un quatrième mécanisme qui est le filtrage PNG.

À vrai dire en théorie je m’attendais au résultat final avec les étoiles disposés horizontalement avec l’étoile moit moit au milieu, le plus surprenant est peut-être que l’image avec l’étoile pleine en premier n’ait pas une taille de fichier plus proche de celle avec l’étoile vide en premier.
Donc en théorie ces deux images devaient produire des fichiers particuliairement petits.


En pratique la première termine 1re, 3e et 3e respectivement avec ScriptPNG, CryoPNG et ImageOptim, alors que la seconde se positionne 4e, 7e et 6e.
Maintenant pourquoi cette disposition devrait-elle favoriser la compression ?
Pour commencer reprennons la toute première image, on remarque que bien qu'elle comporte 19 étoiles elle ne nécessite même pas le double de la taille des fichiers qui ne contiennent que trois étoiles (6475 octets contre 3516 octets). Ceci s'explique assez facilement car la compression PNG à proprement gommée les étoiles identiques successives.


Cette représentation de l’efficacité de la compression PNG est produite par pngthermal qui utilise l’échelle suivante.

Pour faire simple plus le bleu est foncé et plus la compression est efficace, en vert et jaune les gains sont plus réduits et à partir du rouge il y a en fait expansion des données.
On constate donc que les mécanismes de compression mis en œuvre n’ont rencontré de difficultés que pour l’équivalent de 4 étoiles. Maintenant on peut se poser la question de savoir pourquoi les deux étoiles de la seconde rangée non pas été gommées vu qu'il y en a de semblables sur la rangée juste au-dessus. En fait « juste au-dessus » est une vision bidimensionnelle avec les distances cartésiennes que l’on utilise couramment mais qui ne s’applique pas vraiment à la compression PNG qui considère le plus souvent les données qui composent l’image comme un espace monodimensionnel (les lignes qui constituent l’image se suivent en mémoire comme si on avait une seule très grande ligne). En pratique cela signifie que pour faire référence à un élément similaire que l’on aimerait recopier tant qu’il est sur la même ligne la distance va être effectivement assez courte, mais s’il se trouve sur une ou plusieurs lignes plus haut il va falloir rembobiner l’intégralité des lignes.
Avec des illustrations c’est probablement plus clair.


Dans premier cas le petit trait noir représente la distance entre la deuxième étoile pleine et la première, celle-ci est relativement courte et pleinement exploitable.
Dans le second cas la zone bleue représente la distance entre la première étoile de la seconde rangée et la fraction d’étoile pleine de la première rangée, c’est bien plus loin, trop loin même car la fenêtre de recherche est limitée à 32768 octets avec PNG, du coup les étoiles de la seconde rangée doivent être encodées une première fois comme si elles n'étaient jamais apparues précédement.
Si l’on tronque les deux dernières étoiles de chaque rangée la distance devient alors inférieure à 32768 octets et il devient possible de recopier les étoiles de la première rangée sur la seconde rangée.


La taille de ce fichier et significativement plus petite que le précédent avec 4257 octets, mais en pratique il ne sert à rien, en fait le fichier le plus utile serait celui avec les 19 étoiles sur la même rangée, après reste à savoir comment on l’ordonne…


Des deux le plus petit est le second avec 4015 octets (l’autre fait 4159 octets), ce qui représente un gain appréciable en comparaison avec le fichier d’origine à 6475 octets.

On voit bien que seules deux étoiles ont été encodées en propre tout le reste à été massivement copié à partir d’éléments préexistants.
À ce point on peut retenir que dans une image PNG des éléments identiques ou partiellement identiques se compresseront mieux s’ils sont situés horizontalement les uns par rapport aux autres.
Avant de revenir sur le cas des trois étoiles, voici un autre exemple pour mieux intégrer la notion de distance.

Voici un extrait d’une capture d’écran du jeu César III, ce dernier bien que n’utilisant que des graphismes de type bitmap tire avantage de la perspective axonométrique (pseudo isométrique) pour restituer un effet tridimensionnel. Ce type de perspective fait toutefois qu’un bâtiment en arrière plan est en fait exactement le même qu’un autre identique en avant plan ce qui devrait normalement être synonyme de très bonne compression. Sauf que…

On constate sur le rendu de pngthermal que seul un nombre réduit de zones ont bénéficiées d’une compression importante du fait de la présence d’un bâtiment identique dans la proximité immédiate.

Sur cette vue les éléments compressés par copie de séries de pixels préexistants ou répétition de motifs apparaissent en couleur d’origine alors que tout le reste est bleuté.

À l’inverse les bâtiments mis en contraste en haut sont identiques à ceux du bas mais déjà en dehors d’atteinte car en dehors de la fenêtre de recherche, ce sont donc des opportunités de forte compression ratées en raison d’une limitation du format PNG.