Quelle est la limite des données de compression sans perte? (s'il existe une telle limite)

Dernièrement, j'ai eu affaire à des algorithmes liés à la compression, et je me demandais quel était le meilleur taux de compression pouvant être atteint par la compression de données sans perte.

Jusqu'à présent, la seule source que j'ai pu trouver sur ce sujet était Wikipedia:

La compression sans perte de données numérisées telles que la vidéo, le film numérisé et l'audio préserve toutes les informations, mais peut rarement faire beaucoup mieux qu'une compression 1: 2 en raison de l'entropie intrinsèque des données.

Malheureusement, l'article de Wikipédia ne contient aucune référence ou citation à l'appui de cette affirmation. Je ne suis pas un expert en compression de données, donc j'apprécierais toute information que vous pourriez fournir à ce sujet, ou si vous pouviez me diriger vers une source plus fiable que Wikipedia.

Je ne sais pas si quelqu'un a encore expliqué pourquoi le nombre magique semble être exactement 1: 2 et non, par exemple, 1: 1.1 ou 1:20.

L'une des raisons est que dans de nombreux cas typiques, près de la moitié des données numérisées sont du bruit , et le bruit (par définition) ne peut pas être compressé.

J'ai fait une expérience très simple:

• J'ai pris une carte grise . À l'œil humain, cela ressemble à un morceau de carton gris neutre et uni. En particulier, il n'y a aucune information .

• Et puis j'ai pris un scanner normal - exactement le type d'appareil que les gens pourraient utiliser pour numériser leurs photos.

• J'ai scanné la carte grise. (En fait, j'ai numérisé la carte grise avec une carte postale. La carte postale était là pour vérifier la santé mentale afin que je puisse m'assurer que le logiciel du scanner ne fait rien d'étrange, comme ajouter automatiquement du contraste lorsqu'il voit la carte grise sans caractéristiques.)

• J'ai recadré une partie de 1000x1000 pixels de la carte grise et l'ai convertie en niveaux de gris (8 bits par pixel).

Ce que nous avons maintenant devrait être un assez bon exemple de ce qui se passe lorsque vous étudiez une partie sans particularité d'une photo numérisée en noir et blanc , par exemple, un ciel clair. En principe, il ne devrait y avoir exactement rien à voir.

Cependant, avec un grossissement plus important, cela ressemble en fait à ceci:

Il n'y a pas de motif clairement visible, mais il n'a pas une couleur grise uniforme. Une partie est probablement due aux imperfections de la carte grise, mais je suppose que la majeure partie est simplement du bruit produit par le scanner (bruit thermique dans la cellule du capteur, amplificateur, convertisseur A / N, etc.). Ressemble à peu près au bruit gaussien; voici l'histogramme (en échelle logarithmique ):

Maintenant, si nous supposons que chaque pixel a sa teinte choisie dans cette distribution, combien d'entropie avons-nous? Mon script Python m'a dit que nous avons jusqu'à 3,3 bits d'entropie par pixel . Et ça fait beaucoup de bruit.

Si c'était vraiment le cas, cela impliquerait que peu importe l'algorithme de compression que nous utilisons, le bitmap 1000x1000 pixels serait compressé, dans le meilleur des cas, dans un fichier de 412500 octets. Et ce qui se passe dans la pratique: j'ai un fichier PNG de 432018 octets, assez proche.

Si nous généralisons un peu trop, il semble que peu importe les photos noir et blanc que je numérise avec ce scanner, j'obtiendrai la somme des éléments suivants:

• informations "utiles" (le cas échéant),
• bruit, env. 3 bits par pixel.

Maintenant, même si votre algorithme de compression comprime les informations utiles en << 1 bits par pixel, vous aurez toujours jusqu'à 3 bits par pixel de bruit incompressible. Et la version non compressée est de 8 bits par pixel. Le taux de compression sera donc de l'ordre de 1: 2, quoi que vous fassiez.

Un autre exemple, avec une tentative de trouver des conditions trop idéalisées:

• Un appareil photo reflex numérique moderne, utilisant le réglage de sensibilité le plus bas (le moins de bruit).
• Une photo floue d'une carte grise (même s'il y avait des informations visibles sur la carte grise, elle serait floue).
• Conversion du fichier RAW en une image en niveaux de gris 8 bits, sans ajouter de contraste. J'ai utilisé des paramètres typiques dans un convertisseur RAW commercial. Le convertisseur essaie de réduire le bruit par défaut. De plus, nous enregistrons le résultat final sous forme de fichier 8 bits - nous jetons, en substance, les bits de poids faible des lectures brutes du capteur!

Et quel a été le résultat final? Il semble beaucoup mieux que ce que j'ai obtenu du scanner; le bruit est moins prononcé et il n'y a exactement rien à voir. Néanmoins, le bruit gaussien est là:

Et l'entropie? 2,7 bits par pixel . La taille du fichier en pratique? 344923 octets pour 1M pixels. Dans le meilleur des cas, avec de la triche, nous avons poussé le taux de compression à 1: 3.

Bien sûr, tout cela n'a rien à voir avec la recherche TCS, mais je pense qu'il est bon de garder à l'esprit ce qui limite vraiment la compression des données numérisées du monde réel. Les progrès dans la conception d'algorithmes de compression plus sophistiqués et de la puissance brute du processeur ne vont pas aider; si vous voulez enregistrer tout le bruit sans perte, vous ne pouvez pas faire mieux que 1: 2.

Connaissez-vous déjà le théorème de codage silencieux de Shannon ? Ce théorème établit des limites théoriques à la compression sans perte. Certains des commentaires des autres semblent supposer que vous connaissez ce théorème, mais d'après la question, je pense que c'est peut-être la réponse que vous cherchez.

$n>0$

1. $n$

2. La solution pratique courante consiste à utiliser 8 bits, si les seuls entiers que vous encoderez sont tous compris entre 1 et 256 (généralisez à 16, 32 et 64 bits si vous le souhaitez).

3. $n+1$$n$$n$

4. $\lceil\log_2 n\rceil$$\lceil\log_2 n\rceil+1$$n$ en binaire, utilisation $\lceil\log_2 n\rceil-1$ (vous n'avez pas besoin du bit le plus à gauche, qui est toujours un, car vous connaissez déjà la valeur de $\lceil\log_2 n\rceil$). Cet encodage utilise au total$2\lceil\log_2 n\rceil-1$ bits, et est une compression utile de $n$, souvent utilisé en pratique. (Notez que dans la littérature, vous trouverez ces résultats notés$\lg n=\max(1,\lceil\log_2 n\rceil)$ pour raccourcir les notations.)

5. Le code gamma n'est pas optimal , dans le sens où il existe d'autres codes qui utilisent moins d'espace pour arbitrairement de nombreux nombres entiers, et plus pour seulement une quantité finie. Une très bonne lecture sur le sujet est "Un algorithme presque optimal pour la recherche illimitée" par Jon Louis Bentley et Andrew Chi-Chih Yao de 1976 (j'aime particulièrement leur lien entre la complexité des algorithmes de recherche et la taille des encodages entiers: I trouver l'un des résultats TCS les plus simples et les plus beaux que je connaisse). L'essentiel est que$2\lceil\log_2 n\rceil-1$ bits est dans un facteur de deux de l'optimal, ce que la plupart conviennent est suffisant dans la pratique étant donné la complexité de meilleures solutions.

6. Pourtant, prenant l'approche «opportuniste» à sa limite, il existe un nombre infini de schémas de compression tirant parti de diverses hypothèses. Une façon de gérer cette infinité de codages opportunistes (c'est-à-dire le schéma de compression) est d'exiger le codage de l'hypothèse elle-même et de prendre en compte la taille du codage de l'hypothèse dans la taille de compression totale. Formellement, cela correspond à encoder à la fois les données compressées et le décodeur , ou plus généralement à encoder un programme qui, une fois exécuté, sort l'objet non compressé: la plus petite taille d'un tel programme s'appelle la complexité de Kolmogorov $K$. Il s'agit d'une construction très théorique dans le sens où, sans limite sur le temps d'exécution du programme,$K$n'est pas calculable. Une solution de contournement facile autour de cette notion est donnée par les programmes auto-délimiteurs de Levin , où vous ne considérez que les programmes avec un temps d'exécution limité (par exemple, dans un facteur constant de la longueur de l'instance d'origine, qui est une limite inférieure sur le complexité de l'algorithme qui doit écrire chaque symbole).

Il y a toute une communauté qui travaille sur la complexité de Kolmogorov et ses variantes, et une autre communauté qui travaille sur la compression sans perte (l'exemple sur les entiers que j'ai utilisé a l'équivalent sur de nombreux autres types de données), j'ai à peine effleuré la surface, et d'autres pourraient ajouter des précisions (Kolmogorov n'est vraiment pas ma spécialité), mais j'espère que cela vous aidera à clarifier votre question, sinon vous donnera nécessairement la réponse que vous espériez :)

(juste une extension de mon commentaire)

(Comme l'a souligné Joe dans sa réponse) Shannon - dans son article de 1948, " Une théorie mathématique de la communication " a formulé la théorie de la compression des données et établi qu'il y a une limite fondamentale à la compression des données sans perte. Cette limite, appelée taux d'entropie, est désignée par H. La valeur exacte de H dépend de la source d'information --- plus précisément, de la nature statistique de la source. Il est possible de compresser la source, sans perte, avec un taux de compression proche de H. Il est mathématiquement impossible de faire mieux que H.

Cependant, certaines classes d'images (par exemple les images médicales en niveaux de gris) sans bords à contraste élevé et avec des transitions de niveau douces peuvent être compressées (pas si efficacement).

JPEG-LS et JPEG2000 semblent être les normes pour le stockage sans perte d'images médicales. Voir ce tableau pour une comparaison des taux de compression (le JPEG-LS obtient une compression légèrement meilleure).

En utilisant la «compression d'image médicale sans perte», j'ai trouvé les articles suivants qui peuvent vous aider:

Une enquête récente (2011) sur les techniques de compression d'images médicales: Techniques de compression d'images médicales bidimensionnelles - Une enquête

... Cet article présente une vue d'ensemble des différentes techniques de compression basées sur les réseaux DCT, DWT, ROI et neuronaux pour les images médicales bidimensionnelles (2D).

Une présentation détaillée de deux algorithmes de compression sans perte standard: JPEG-LS et JPG2000 en mode sans perte: Compression sans perte d'images médicales en niveaux de gris - Efficacité des approches traditionnelles et de pointe

... Trois mille six cent soixante-dix-neuf (3 679) images en niveaux de gris à une seule image provenant de plusieurs régions anatomiques, modalités et fournisseurs, ont été testées. ...

Une autre enquête: une enquête sur les techniques de compression d'images médicales contemporaines

ÉDITER

Peut-être vous demandez-vous toujours "Qu'est-ce que l'enfer est l'entropie d'une image?" ... OK, c'est la quantité d'informations contenues dans l'image ... mais pour mieux la comprendre, vous devriez lire quelque chose sur les 3 phases habituellement utilisées dans la compression d'image :

• transformation (par exemple, transformation d'ondelettes discrète)
• quantification
• encodage entropique

Vous pouvez utiliser Google pour rechercher un didacticiel ou un livre sur la compression d'images (par exemple un didacticiel rapide ), ou essayer de regarder une vidéo technique en ligne (par exemple, leçon 16 - Introduction au codage d'images et de vidéos ).

Considérez un fichier comme une chaîne.

Vous ne pouvez jamais faire mieux que la complexité de Kolmogorov d'une chaîne (c'est par la définition de la complexité de Komogorov).

Fixez une longueur de chaîne. Alors maintenant, nous ne regardons que les chaînes de longueur n.

La moitié de toutes ces chaînes peut être compressée d'au plus 1 bit. 1/4 de toutes les chaînes peut être compressé par au plus 2 bits. 1/8 de toutes ces chaînes peuvent être compressées par au plus 3 bits.

Quelle fraction des chaînes (images, fichiers, etc.) peut être compressée au rapport 2: 1 - très, très peu. Alors pourquoi la compression fonctionne-t-elle? Parce que presque toutes les données que de vraies personnes essaient de compresser sont très structurées - elles ne ressemblent pas à un fichier aléatoire. Plus les données sont aléatoires, plus elles sont difficiles à compresser. Ils vont de pair. La plupart des chaînes semblent aléatoires.

Pour voir cela en action, générez un fichier aléatoire en utilisant un processus aléatoire. Je veux dire un fichier vraiment, vraiment aléatoire. Essayez maintenant de le compresser en utilisant votre algorithme de compression préféré. Il conservera la même taille ou grossira, presque tout le temps.

D'un autre côté, il y a des cordes très compressibles. Prenez la chaîne suivante: 100000..000 (1 suivi d'un million de zéros). La description de celui-ci s'inscrit dans la phrase précédente, et un ordinateur pourrait le reconstruire à partir de cette description (ou d'une version très similaire). Pourtant, cette description est loin d'un million de chiffres.

Le fait est que les chaînes ayant cette propriété (d'être hautement compressibles) sont extrêmement rares parmi toutes les chaînes possibles. Le fait secondaire est que presque toutes les données générées par l'homme sont super, super compressibles parce qu'elles sont si structurées.