Entropie d'une image

Quelle est la façon correcte le plus théorique / physique-théorique de calculer l'entropie d'une image? Je ne me soucie pas de l'efficacité informatique en ce moment - je la veux théoriquement aussi correcte que possible.

Commençons par une image en niveaux de gris. Une approche intuitive consiste à considérer l'image comme un sac de pixels et à calculer où est le nombre de niveaux de gris et est la probabilité associée au niveau de gris .

Il y a deux problèmes avec cette définition:

1. Cela fonctionne pour une bande (c'est-à-dire en niveaux de gris), mais comment doit-on l'étendre de manière statistiquement correcte à plusieurs bandes? Par exemple, pour 2 bandes, faut-il se baser sur et donc sur PMF en utilisant ? Si on a plusieurs bandes ( >> 2) alors , ce qui semble faux.$(X_1,X_2)$$P(X_1=x_1,X_2=x_2)$$B$$P(X_1=x_1, ..., X_B=x_B) \sim 1/N^B \rightarrow H_{MAX}$
2. Les informations spatiales ne sont pas prises en compte. Par exemple, les images ci-dessous (garde de John Loomis ) ont le même , bien qu'elles ne véhiculent clairement pas les mêmes informations.$H$

Quelqu'un souhaite-t-il expliquer ou donner des conseils, ou me référer à un matériel de référence décent sur le sujet? Je m'intéresse principalement à une approche théoriquement correcte du second problème (ie l'information spatiale).

"Quelle est la manière correcte le plus théorique / physique-théorique de calculer l'entropie d'une image?"

Une excellente et opportune question.

Contrairement à la croyance populaire, il est en effet possible de définir intuitivement (et théoriquement) l'entropie naturelle d'informations pour une image.

Considérez la figure suivante:

Nous pouvons voir que l'image différentielle a un histogramme plus compact, donc son entropie d'information de Shannon est plus faible. Nous pouvons donc obtenir une redondance plus faible en utilisant l'entropie de Shannon du second ordre (c'est-à-dire l'entropie dérivée de données différentielles). Si nous pouvons étendre cette idée de manière isotrope en 2D, alors nous pourrions nous attendre à de bonnes estimations pour l'entropie des informations d'image.

Un histogramme bidimensionnel de gradients permet l'extension 2D.

Nous pouvons formaliser les arguments et, en fait, cela a été achevé récemment. Récapitulant brièvement:

L'observation selon laquelle la définition simple (voir par exemple la définition MATLAB de l'entropie d'image) ignore la structure spatiale est cruciale. Pour comprendre ce qui se passe, il convient de revenir brièvement sur le cas 1D. On sait depuis longtemps que l'utilisation de l'histogramme d'un signal pour calculer ses informations / entropie de Shannon ignore la structure temporelle ou spatiale et donne une mauvaise estimation de la compressibilité ou de la redondance inhérente au signal. La solution était déjà disponible dans le texte classique de Shannon; utiliser les propriétés du second ordre du signal, c'est-à-dire les probabilités de transition. L’observation de 1971 (Rice & Plaunt) que le meilleur prédicteur d'une valeur de pixel dans une numérisation raster est la valeur du pixel précédent conduit immédiatement à un prédicteur différentiel et à une entropie de Shannon du second ordre qui s'aligne avec des idées de compression simples telles que l'encodage de la longueur d'exécution. Ces idées ont été affinées à la fin des années 80, ce qui a donné lieu à certaines techniques classiques de codage sans perte (différentielle) qui sont toujours utilisées (PNG, JPG sans perte, GIF, JPG 2000 sans perte) tandis que les ondelettes et les DCT ne sont utilisés que pour le codage avec perte.

Passons maintenant à 2D; les chercheurs ont trouvé très difficile d'étendre les idées de Shannon à des dimensions plus élevées sans introduire une dépendance d'orientation. Intuitivement, on pourrait s'attendre à ce que l'entropie d'information de Shannon d'une image soit indépendante de son orientation. Nous nous attendons également à ce que les images avec une structure spatiale complexe (comme l'exemple de bruit aléatoire du questionneur) aient une entropie d'information plus élevée que les images avec une structure spatiale simple (comme l'exemple de l'échelle de gris lisse du questionneur). Il s'avère que la raison pour laquelle il était si difficile d'étendre les idées de Shannon de 1D à 2D est qu'il existe une asymétrie (unilatérale) dans la formulation originale de Shannon qui empêche une formulation symétrique (isotrope) en 2D. Une fois l'asymétrie 1D corrigée, l'extension 2D peut se dérouler facilement et naturellement.

Couper au but (les lecteurs intéressés peuvent consulter l'exposé détaillé dans la préimpression arXiv à https://arxiv.org/abs/1609.01117 ) où l'entropie d'image est calculée à partir d'un histogramme 2D de gradients (fonction de densité de probabilité de gradient).

Tout d'abord, le pdf 2D est calculé par des estimations de binning des images dérivées x et y. Cela ressemble à l'opération de binning utilisée pour générer l'histogramme d'intensité le plus courant dans 1D. Les dérivées peuvent être estimées par des différences finies de 2 pixels calculées dans les directions horizontale et verticale. Pour une image carrée NxN f (x, y), nous calculons les valeurs NxN des dérivées partielles fx et les valeurs NxN de fy. Nous parcourons l'image différentielle et pour chaque pixel que nous utilisons (fx, fy) pour localiser un bac discret dans le tableau de destination (pdf 2D) qui est ensuite incrémenté de un. Nous répétons pour tous les pixels NxN. Le pdf 2D résultant doit être normalisé pour avoir une probabilité unitaire globale (la simple division par NxN permet cela). Le pdf 2D est maintenant prêt pour la prochaine étape.

Le calcul de l'entropie d'information de Shannon 2D à partir du pdf de gradient 2D est simple. La formule de sommation logarithmique classique de Shannon s'applique directement, sauf pour un facteur crucial de moitié qui provient de considérations d'échantillonnage limitées par la bande spéciale pour une image en dégradé (voir l'article arXiv pour plus de détails). Le demi-facteur rend l'entropie 2D calculée encore plus faible par rapport à d'autres méthodes (plus redondantes) d'estimation de l'entropie 2D ou de la compression sans perte.

Je suis désolé de ne pas avoir écrit les équations nécessaires ici, mais tout est disponible dans le texte préimprimé. Les calculs sont directs (non itératifs) et la complexité de calcul est d'ordre (le nombre de pixels) NxN. L'entropie d'information de Shannon calculée finale est indépendante de la rotation et correspond précisément au nombre de bits requis pour coder l'image dans une représentation en gradient non redondante.

Soit dit en passant, la nouvelle mesure d'entropie 2D prédit une entropie (agréablement intuitive) de 8 bits par pixel pour l'image aléatoire et de 0,000 bits par pixel pour l'image à gradient lisse dans la question d'origine.

Il n'y en a pas, tout dépend du contexte et de vos informations préalables. L'entropie a de nombreuses interprétations telles que «mesure de l'ordre» ou «mesure de l'information», mais au lieu de regarder les interprétations, vous pouvez simplement regarder ce qu'elle est réellement. L'entropie n'est qu'un moyen d'exprimer le nombre d'états d'un système. Un système avec plusieurs états a une entropie élevée et un système avec peu d'états a une entropie faible.

Vous et l'article auquel vous vous connectez - indique que les deux images ont la même entropie. Ce n'est pas correct (pour moi).

L'article calcule correctement l'entropie.

L'entropie est donc:

Cependant, ce n'est pas le cas pour la deuxième image.

L'entropie peut toujours être calculée comme suit:

$p_k = \frac{1}{M} = 2^{-n}$$p_1$$p_2, p_3, p_4 \ldots p_{many}$

Par conséquent, les deux images n'ont pas la même entropie.

Il peut sembler contre-intuitif que l'entropie dépende de la façon dont vous regardez le problème. Cependant, vous le savez probablement par compression. La compression maximale d'un fichier est dictée par le théorème de codage source de Shannon qui définit une limite supérieure pour la façon dont un algorithme de compression peut compresser un fichier. Cette limite dépend de l'entropie du fichier. Tous les compresseurs modernes compresseront un fichier proche de cette limite.

Cependant, si vous savez que le fichier est un fichier audio, vous pouvez le compresser en utilisant FLAC au lieu d'un compresseur générique. FLAC est sans perte, donc toutes les informations sont préservées. FLAC ne peut pas contourner le théorème de codage source de Shannon, c'est des mathématiques, mais il peut regarder le fichier d'une manière qui réduit l'entropie du fichier, donc faire une meilleure compression.

Identiquement, quand je vous regarde la deuxième image, je vois que les pixels sont triés par valeur de gris, et donc elle n'a pas la même entropie pour moi que l'image avec un bruit aléatoire.

L'idée d' entropie est essentiellement quelque chose comme "un nombre de micro-états cohérents avec le macrostate".

$p[\,I,h\,]$$I$$p[\,h\mid I\,]$

$h$$I$

ne fonctionne PAS dans la pratique, pour la simple raison qu'il est presque impossible de déterminer Pk. Vous pensez que vous pouvez le faire, comme vous l'avez fait en considérant le nombre de niveaux de gris. Pk n'est pas ça. Pk est toutes les combinaisons possibles de niveaux de gris. Vous devez donc créer un arbre de probabilité multidimensionnel en considérant 1, 2, 3 ... combinaisons de pixels. Si vous lisez le travail de Shannon, vous le voyez faire ce calcul pour un anglais simple en considérant une profondeur d'arbre de 3 lettres. Il devient alors difficile à manier sans ordinateur.

Vous l'avez prouvé vous-même avec l'énoncé 2. C'est pourquoi votre calcul d'entropie renvoie le même niveau d'entropie pour les deux images, même si l'une est clairement moins ordonnée que l'autre.

Il n'y a pas non plus un tel concept de distribution spatiale dans le calcul d'entropie. S'il y en avait, vous devrez également calculer l'entropie différemment pour les échantillons distribués temporellement. Et que feriez-vous pour un tableau de données à 11 dimensions? Pour l'entropie informationnelle; il est mesuré en octets.

Compressez simplement les images à l'aide d'un algorithme de compression. Il produira une estimation de l'entropie en octets. Il le fera pour toute image ou littéralement tout ce qui peut être numérisé, comme la musique ou les pièces shakespeariennes.

Donc. Votre image aléatoire contient environ 114 Ko, et votre image commandée contient environ 2,2 Ko. C'est ce à quoi vous vous attendez, mais vous le saviez déjà un peu parce que vous avez vu que les tailles des fichiers image étaient de cette taille. J'ai réduit la taille compressée de 33% pour permettre de futures améliorations des algorithmes de compression. Je ne peux pas les voir s'améliorer au-delà de cela car la courbe d'amélioration devient asymptotique à une vraie valeur sous-jacente.

PS Par intérêt, Shakespeare n'a produit que 1 Moctet d'entropie dans toute sa vie, calculé par cette technique. La plupart du temps, c'est assez bon.