Comment le format PNG sans perte est-il basé sur un paramètre de compression?

Les fichiers PNG utilisent une compression sans perte. Cependant, chaque fois que je suis dans un éditeur d'image, tel que GIMP et que j'essaie d'enregistrer une image au format PNG, le paramètre de compression, compris entre 0 et 9, est demandé. S'il contient un paramètre de compression qui affecte la précision visuelle de l'image compressée, comment rend-il le format PNG sans perte?

Est-ce que je n'ai un comportement sans perte que lorsque je règle le paramètre de compression sur 9?

La PNG est sans perte. GIMP n'utilise probablement pas le meilleur mot dans ce cas. Voyez cela comme une "qualité de compression" ou, en d'autres termes, un "niveau de compression". Avec une compression plus faible, vous obtenez un fichier plus volumineux, mais sa production prend moins de temps, tandis qu'avec une compression plus élevée, vous obtenez un fichier plus petit, plus long à produire. Généralement, vous obtenez des rendements décroissants (c’est-à-dire que la taille ne diminue pas autant par rapport à l’augmentation du temps nécessaire) lorsque vous atteignez les niveaux de compression les plus élevés, mais cela dépend de vous.

PNG est compressé, mais sans perte

Le niveau de compression est un compromis entre la taille du fichier et la vitesse de codage / décodage. Pour trop généraliser, même les formats sans image, tels que FLAC, ont des concepts similaires.

Différents niveaux de compression, même sortie décodée

Bien que les tailles de fichier soient différentes, en raison des niveaux de compression différents, la sortie décodée réelle sera identique.

Vous pouvez comparer les valeurs de hachage MD5 des sorties décodées à l’ ffmpegutilisation du multiplexeur MD5 .

Ceci est mieux illustré par quelques exemples:

Créer des fichiers PNG:

$ ffmpeg -i input -vframes 1 -compression_level 0 0.png
$ ffmpeg -i input -vframes 1 -compression_level 100 100.png

• Par défaut ffmpeg, utilisera -compression_level 100pour la sortie PNG.

Comparer la taille du fichier:

$ du -h *.png
  228K    0.png
  4.0K    100.png

Décodez les fichiers PNG et affichez les hachages MD5:

$ ffmpeg -loglevel error -i 0.png -f md5 -
3d3fbccf770a51f9d81725d4e0539f83

$ ffmpeg -loglevel error -i 100.png -f md5 -
3d3fbccf770a51f9d81725d4e0539f83

Puisque les deux hachages sont identiques, vous pouvez être assuré que les sorties décodées (la vidéo brute non compressée) sont exactement les mêmes.

La compression PNG se fait en deux étapes.

1. La pré-compression réorganise les données d'image de sorte qu'elles soient plus compressibles par un algorithme de compression à usage général.
2. La compression proprement dite est effectuée par DEFLATE, qui recherche et élimine les séquences d'octets dupliquées en les remplaçant par des jetons courts.

Etant donné que l'étape 2 est une tâche très consommatrice de temps et de ressources, la bibliothèque zlib sous-jacente (encapsulation de DEFLATE brut) prend un paramètre de compression compris entre 1 = compression la plus rapide, 9 = meilleure compression, 0 = aucune compression. C'est de là que vient la plage 0-9, et GIMP transmet simplement ce paramètre à zlib. Observez qu'au niveau 0, votre png sera légèrement plus grand que le bitmap équivalent.

Cependant, le niveau 9 n’est que le "meilleur" que tentera zlib et reste une solution de compromis .
Pour vraiment vous en rendre compte, si vous êtes prêt à dépenser 1000 fois plus de puissance de traitement pour une recherche exhaustive, vous pouvez obtenir une densité de données supérieure de 3 à 8% en utilisant zopfli au lieu de zlib.
La compression est toujours sans perte, c'est simplement une représentation DEFLATE plus optimale des données. Cela approche les limites des bibliothèques compatibles avec zlib, et constitue donc la véritable "meilleure" compression possible avec PNG.

Une des principales motivations du format PNG était de créer un remplacement du GIF non seulement gratuit, mais aussi une amélioration par rapport à l'essentiel. De ce fait, la compression PNG est totalement sans perte, c’est-à-dire que les données de l’image originale peuvent être reconstruites exactement, bit par bit, comme dans le format GIF et la plupart des formats de format TIFF.

PNG utilise un processus de compression en deux étapes:

1. Pré-compression: filtrage (prédiction)
2. Compression: DEFLATE (voir wikipedia )

L'étape de précompression s'appelle le filtrage. Il s'agit d'une méthode de transformation réversible des données d'image afin que le moteur de compression principal puisse fonctionner plus efficacement.

À titre d’exemple simple, considérons une séquence d’octets augmentant uniformément de 1 à 255:

1, 2, 3, 4, 5, .... 255

Comme il n'y a pas de répétition dans la séquence, cela compresse très mal ou pas du tout. Mais une modification triviale de la séquence - à savoir, laisser le premier octet seul mais remplacer chaque octet suivant par la différence entre lui et son prédécesseur - transforme la séquence en un ensemble extrêmement compressible:

1, 1, 1, 1, 1, .... 1

La transformation ci-dessus est sans perte car aucun octet n'a été omis et est entièrement réversible. La taille comprimée de cette série sera beaucoup réduite, mais la série originale peut toujours être parfaitement reconstituée.

Les données d'image réelles sont rarement aussi parfaites, mais le filtrage améliore la compression des images en niveaux de gris et truecolor et peut également aider certaines images en palette. PNG prend en charge cinq types de filtres et un encodeur peut choisir d’utiliser un filtre différent pour chaque ligne de pixels de l’image:

L'algorithme fonctionne sur les octets, mais pour les grands pixels (par exemple, RVB 24 bits ou RGBA 64 bits), seuls les octets correspondants sont comparés, ce qui signifie que les composantes rouges des couleurs de pixels sont traitées séparément des composantes de pixels verte et bleue.

Pour choisir le meilleur filtre pour chaque ligne, un encodeur doit tester toutes les combinaisons possibles. Ceci est clairement impossible, car même une image de 20 lignes nécessiterait des tests de plus de 95 trillions de combinaisons, où "tester" impliquerait de filtrer et de compresser toute l'image.

Les niveaux de compression sont normalement définis comme des nombres compris entre 0 (aucun) et 9 (meilleur). Celles-ci font référence à des compromis entre vitesse et taille, et concernent le nombre de combinaisons de filtres de lignes à essayer. Il n'y a pas de normes concernant ces niveaux de compression, donc chaque éditeur d'image peut avoir ses propres algorithmes quant au nombre de filtres à essayer lors de l'optimisation de la taille de l'image.

Le niveau de compression 0 signifie que les filtres ne sont pas utilisés du tout, ce qui est rapide mais inutile. Des niveaux plus élevés signifient que de plus en plus de combinaisons sont essayées sur les rangées d'images et que seules les meilleures sont retenues.

Je suppose que l’approche la plus simple pour obtenir la meilleure compression consiste à tester, compresser de manière incrémentielle chaque ligne avec chaque filtre, à enregistrer le plus petit résultat et à répéter l'opération pour la ligne suivante. Cela revient à filtrer et à compresser l’ensemble de l’image cinq fois, ce qui peut constituer un compromis raisonnable pour une image qui sera transmise et décodée plusieurs fois. Des valeurs de compression inférieures feront moins, à la discrétion du développeur de l'outil.

En plus des filtres, le niveau de compression peut également affecter le niveau de compression zlib, qui est un nombre compris entre 0 (pas de déflation) et 9 (déflation maximale). La manière dont les niveaux 0 à 9 spécifiés affectent l'utilisation des filtres, qui constituent la principale fonctionnalité d'optimisation de PNG, dépend toujours du développeur de l'outil.

La conclusion est que PNG a un paramètre de compression qui peut réduire la taille du fichier de manière très significative, le tout sans perdre un seul pixel.

Sources:

Documentation portable de Wikipedia sur les réseaux graphiques
libpng Chapitre 9 - Compression et filtrage

OK, je suis trop tard pour la prime, mais voici ma réponse quand même.

La PNG est toujours sans perte . Il utilise l'algorithme Deflate / Inflate, similaire à ceux utilisés dans les programmes zip.

L'algorithme Deflate recherche des séquences d'octets répétées et les remplace par des balises. Le paramètre de niveau de compression spécifie l'effort que le programme utilise pour trouver la combinaison optimale de séquences d'octets et la quantité de mémoire réservée à cette fin. C'est un compromis entre le temps et l'utilisation de la mémoire par rapport à la taille du fichier compressé. Cependant, les ordinateurs modernes sont si rapides et disposent de suffisamment de mémoire pour qu'il soit rarement nécessaire d'utiliser un paramètre autre que le paramètre de compression le plus élevé.

De nombreuses implémentations PNG utilisent la bibliothèque zlib pour la compression. Zlib a neuf niveaux de compression, 1-9. Je ne connais pas les composants internes de Gimp, mais comme il a des paramètres de niveau de compression compris entre 0 et 9 (0 = pas de compression), je suppose que ce paramètre sélectionne simplement le niveau de compression de zlib.

L'algorithme Deflate est un algorithme de compression à usage général , il n'a pas été conçu pour la compression d'images. Contrairement à la plupart des autres formats de fichier image sans perte, le format PNG n’est pas limité à cela. La compression PNG tire parti de la connaissance que nous comprimons une image 2D . Ceci est réalisé par ce qu'on appelle des filtres .

(Filtre est en réalité un terme un peu trompeur. Il ne modifie pas réellement le contenu de l'image, il la code simplement différemment. Un nom plus précis serait le codeur delta.)

La spécification PNG spécifie 5 filtres différents (dont 0 = aucun). Le filtre remplace les valeurs absolues de pixels par la différence entre le pixel précédent , le haut, la diagonale ou une combinaison de celles-ci. Cela peut améliorer considérablement le taux de compression. Chaque ligne de balayage sur l'image peut utiliser un filtre différent. Le codeur peut optimiser la compression en choisissant le meilleur filtre pour chaque ligne.

Pour plus de détails sur le format de fichier PNG, voir Spécification PNG .

Comme le nombre de combinaisons est pratiquement infini, il n’est pas possible de toutes les essayer. Par conséquent, différents types de stratégies ont été développés pour trouver une combinaison efficace. La plupart des éditeurs d'images n'essaient probablement même pas d'optimiser les filtres ligne par ligne, mais utilisaient plutôt un filtre fixe (très probablement Paeth).

Un programme en ligne de commande pngcrush essaie plusieurs stratégies pour trouver le meilleur résultat. Cela peut réduire considérablement la taille du fichier PNG créé par d'autres programmes, mais cela peut prendre un peu de temps pour des images plus grandes. Voir Source Forge - pngcrush .

Le niveau de compression dans les éléments sans perte est toujours juste le trading de ressources encodées (généralement du temps, parfois aussi de la RAM) par rapport au débit. La qualité est toujours à 100%.

Bien sûr, les compresseurs sans perte ne peuvent JAMAIS garantir une compression réelle. Les données aléatoires sont incompressibles, il n'y a pas de modèle à trouver ni de similitude. Shannon théorie de l'information et tout ça. L’intérêt de la compression de données sans perte est que les humains travaillent généralement avec des données hautement aléatoires, mais pour la transmission et le stockage, nous pouvons les compresser en aussi peu de bits que possible. Espérons que cela se rapproche le plus possible de la complexité de Kolmogorov de l'original.

Qu'il s'agisse de données génériques zip ou 7z, d'images png, d'audio flac ou de vidéos h.264 (en mode sans perte), c'est la même chose. Avec certains algorithmes de compression, tels que lzma (7zip) et bzip2, augmenter le paramètre de compression augmente le temps CPU de DECODER (bzip2) ou plus souvent la quantité de RAM nécessaire (lzma et bzip2 et h.264 avec davantage de cadres de référence) . Le décodeur doit souvent enregistrer davantage de sorties décodées dans la RAM car le décodage de l'octet suivant pourrait faire référence à un octet décodé il y a plusieurs mégaoctets (par exemple, une image vidéo qui ressemble le plus à celle d'une demi-seconde auparavant serait encodée avec des références à 12 images ). Même chose avec bzip2 et en choisissant une taille de bloc importante, mais cela décompresse aussi plus lentement. Lzma a un dictionnaire de taille variable, et vous pouvez créer des fichiers nécessitant 1.

Premièrement, la PNG est toujours sans perte. Le paradoxe apparent est dû au fait qu'il existe deux types de compression possibles (pour tout type de données): avec perte et sans perte.

La compression sans perte comprime les données (c.-à-d. La taille du fichier) en utilisant diverses astuces, en conservant tout et sans approximation. En conséquence, il est possible que la compression sans perte ne puisse pas compresser les choses du tout. (Techniquement, les données avec une entropie élevée peuvent être très difficiles, voire impossibles, à compresser pour des méthodes sans perte.) La compression avec pertes se rapproche des données réelles, mais l'approximation est imparfaite, mais cette "suppression" de précision permet généralement une meilleure compression.

Voici un exemple trivial de compression sans perte: si vous avez une image composée de 1 000 pixels noirs, au lieu de stocker la valeur pour le noir 1 000 fois, vous pouvez stocker un nombre (1000) et une valeur (noir), compressant ainsi un pixel 1000 " image "en seulement deux chiffres. (Il s'agit d'une forme brute d'une méthode de compression sans perte appelée codage de longueur d'exécution).