Entropie eines Bildes

Was ist die informations- / physikalisch-theoretisch korrekteste Methode, um die Entropie eines Bildes zu berechnen? Die Recheneffizienz ist mir momentan egal - ich möchte, dass sie theoretisch so korrekt wie möglich ist.

Beginnen wir mit einem Graustufenbild. Eine intuitive Vorgehensweise ist das Bild als eine Tasche von Pixeln zu prüfen und berechnen , wobei K die Anzahl der Graustufen und p k die Wahrscheinlichkeit ist, die mit Graustufen - k .

Bei dieser Definition gibt es zwei Probleme:

1. Es funktioniert für ein Band (dh Graustufen), aber wie sollte man es statistisch korrekt auf mehrere Bänder ausweiten? Soll man sich zum Beispiel für 2 Bänder auf und damit auf PMF mit P stützen ( X 1 = x 1 , X 2 = x 2 ) ? Wenn man hat viele ( B >> 2) Bänder dann P ( X 1 = x 1 , . . . , X B = x B ) $(X_1,X_2)$$P(X_1=x_1,X_2=x_2)$$B$ , was falsch zu sein scheint.$P(X_1=x_1, ..., X_B=x_B) \sim 1/N^B \rightarrow H_{MAX}$
2. Rauminformationen werden nicht berücksichtigt. Zum Beispiel haben die Bilder unten (das Sorgerecht für John Loomis ) dasselbe , obwohl sie eindeutig nicht die gleichen Informationen enthalten.$H$

Möchte jemand etwas erklären, Ratschläge erteilen oder mich auf ein anständiges Referenzmaterial zu diesem Thema verweisen? Ich interessiere mich hauptsächlich für eine theoretisch korrekte Herangehensweise an das zweite Problem (dh räumliche Information).

„Wie lässt sich die Entropie eines Bildes am besten informations- / physikalisch-theoretisch richtig berechnen?“

Eine ausgezeichnete und aktuelle Frage.

Entgegen der landläufigen Meinung ist es tatsächlich möglich, eine intuitive (und theoretisch) natürliche Informationsentropie für ein Bild zu definieren.

Betrachten Sie die folgende Abbildung:

Wir können sehen, dass das Differenzbild ein kompakteres Histogramm aufweist, weshalb seine Shannon-Informationsentropie geringer ist. Wir können also eine geringere Redundanz erzielen, indem wir die Shannon-Entropie zweiter Ordnung verwenden (dh die Entropie, die aus Differentialdaten abgeleitet wird). Wenn wir diese Idee isotrop in 2D erweitern können, können wir gute Schätzungen für die Bildinformationsentropie erwarten.

Ein zweidimensionales Histogramm von Verläufen ermöglicht die 2D-Erweiterung.

Wir können die Argumente formalisieren und dies ist in der Tat vor kurzem abgeschlossen worden. Kurz zusammengefasst:

Die Beobachtung, dass die einfache Definition (siehe zum Beispiel MATLABs Definition der Bildentropie) die räumliche Struktur ignoriert, ist entscheidend. Um zu verstehen, was los ist, lohnt es sich, kurz auf den 1D-Fall zurückzukommen. Es ist seit langem bekannt, dass die Verwendung des Histogramms eines Signals zur Berechnung seiner Shannon-Information / Entropie die zeitliche oder räumliche Struktur ignoriert und eine schlechte Schätzung der inhärenten Kompressibilität oder Redundanz des Signals liefert. Die Lösung war bereits in Shannons klassischem Text enthalten. Verwenden Sie die Eigenschaften zweiter Ordnung des Signals, dh Übergangswahrscheinlichkeiten. Die Beobachtung im Jahr 1971 (Rice & Die Annahme, dass der beste Prädiktor eines Pixelwerts in einer Rasterabtastung der Wert des vorhergehenden Pixels ist, führt sofort zu einem Differentialprädiktor und einer Shannon-Entropie zweiter Ordnung, die mit einfachen Komprimierungsideen wie Lauflängencodierung übereinstimmt. Diese Ideen wurden in den späten 80er Jahren verfeinert, was zu einigen klassischen verlustfreien Bildcodierungstechniken (Differenzialcodierung) führte, die immer noch verwendet werden (PNG, verlustfreies JPG, GIF, verlustfreies JPG2000), während Wavelets und DCTs nur für verlustbehaftete Codierung verwendet werden.

Jetzt zu 2D übergehen; Die Forscher fanden es sehr schwierig, Shannons Ideen auf höhere Dimensionen auszuweiten, ohne eine Orientierungsabhängigkeit einzuführen. Intuitiv könnte man erwarten, dass die Shannon-Informationsentropie eines Bildes unabhängig von seiner Orientierung ist. Wir erwarten auch, dass Bilder mit einer komplizierten räumlichen Struktur (wie das Beispiel des zufälligen Rauschens des Fragestellers) eine höhere Informationsentropie aufweisen als Bilder mit einer einfachen räumlichen Struktur (wie das Beispiel des Fragestellers mit glatten Graustufen). Es stellt sich heraus, dass es so schwierig war, Shannons Ideen von 1D auf 2D zu erweitern, weil Shannons ursprüngliche Formulierung eine (einseitige) Asymmetrie aufweist, die eine symmetrische (isotrope) Formulierung in 2D verhindert. Sobald die 1D-Asymmetrie korrigiert ist, kann die 2D-Erweiterung einfach und natürlich erfolgen.

Auf den Punkt gebracht (interessierte Leser können die ausführliche Darstellung im arXiv-Preprint unter https://arxiv.org/abs/1609.01117 nachlesen ), wo die Bildentropie aus einem 2D-Histogramm von Verläufen berechnet wird (Gradientenwahrscheinlichkeitsdichtefunktion).

Zunächst wird das 2D-PDF durch Binning-Schätzungen der x- und y-Ableitungen der Bilder berechnet. Dies ähnelt der Binning-Operation, mit der das in 1D üblichere Intensitätshistogramm erstellt wird. Die Ableitungen können durch endliche Differenzen von 2 Pixeln geschätzt werden, die in horizontaler und vertikaler Richtung berechnet werden. Für ein NxN-Quadratbild f (x, y) berechnen wir NxN-Werte der partiellen Ableitung fx und NxN-Werte von fy. Wir scannen das Differenzbild und suchen für jedes Pixel, das wir verwenden (fx, fy), eine diskrete Bin im Ziel-Array (2D-PDF), die dann um eins erhöht wird. Wir wiederholen für alle NxN Pixel. Das resultierende 2D-PDF muss normalisiert werden, um die Gesamtwahrscheinlichkeit der Einheit zu erhalten (dies wird einfach durch NxN dividiert). Das 2D-PDF ist jetzt bereit für die nächste Stufe.

Die Berechnung der 2D-Shannon-Informationsentropie aus dem 2D-Gradienten-PDF ist einfach. Die klassische logarithmische Summationsformel von Shannon gilt direkt, mit Ausnahme eines entscheidenden Faktors von der Hälfte, der aus speziellen Überlegungen zur bandbegrenzten Abtastung für ein Gradientenbild stammt (Einzelheiten siehe arXiv-Artikel). Der halbe Faktor verringert die berechnete 2D-Entropie im Vergleich zu anderen (redundanteren) Methoden zur Schätzung der 2D-Entropie oder der verlustfreien Komprimierung.

Es tut mir leid, dass ich hier nicht die notwendigen Gleichungen geschrieben habe, aber alles ist im Preprint-Text verfügbar. Die Berechnungen sind direkt (nicht iterativ) und die Komplexität der Berechnung ist in der Größenordnung (Anzahl der Pixel) NxN. Die endgültig berechnete Shannon-Informationsentropie ist rotationsunabhängig und entspricht genau der Anzahl von Bits, die zum Codieren des Bildes in einer nicht redundanten Gradientendarstellung erforderlich sind.

Übrigens sagt das neue 2D-Entropiemaß eine (intuitiv ansprechende) Entropie von 8 Bit pro Pixel für das Zufallsbild und 0,000 Bit pro Pixel für das glatte Gradientenbild in der ursprünglichen Frage voraus.

Es gibt keine, alles hängt vom Kontext und Ihren vorherigen Informationen ab. Entropie hat viele Interpretationen wie "Messung der Ordnung" oder "Messung der Information", aber anstatt sich die Interpretationen anzusehen, könnte man sich einfach ansehen, was es tatsächlich ist. Entropie ist nur ein Ausdruck für die Anzahl der Zustände eines Systems. Ein System mit vielen Zuständen hat eine hohe Entropie, und ein System mit wenigen Zuständen hat eine niedrige Entropie.

Sie und der Artikel, auf den Sie verweisen - besagen, dass die beiden Bilder dieselbe Entropie haben. Das ist nicht richtig (für mich).

Der Artikel berechnet korrekt die Entropie.

Daher ist die Entropie:

Dies ist jedoch beim zweiten Bild nicht der Fall.

Die Entropie kann immer noch wie folgt berechnet werden:

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

Daher haben die beiden Bilder nicht die gleiche Entropie.

Es mag widersprüchlich erscheinen, dass die Entropie davon abhängt, wie Sie das Problem betrachten. Sie kennen es jedoch wahrscheinlich aus der Komprimierung. Die maximale Komprimierung einer Datei wird durch das Shannon's Source Coding Theorem vorgegeben, das eine Obergrenze dafür festlegt, wie gut ein Komprimierungsalgorithmus eine Datei komprimieren kann. Diese Grenze hängt von der Entropie der Datei ab. Alle modernen Kompressoren komprimieren eine Datei, die nahe an dieser Grenze liegt.

Wenn Sie jedoch wissen, dass es sich bei der Datei um eine Audiodatei handelt, können Sie sie mit FLAC anstelle eines generischen Kompressors komprimieren. FLAC ist verlustfrei, sodass alle Informationen erhalten bleiben. FLAC kommt nicht um den Quellcode-Satz von Shannon herum, das ist Mathematik, aber es kann die Datei auf eine Art und Weise betrachten, die die Entropie der Datei verringert und somit eine bessere Komprimierung bewirkt.

Wenn ich Ihnen das zweite Bild ansehe, sehe ich, dass die Pixel nach Grauwerten sortiert sind und daher nicht die gleiche Entropie für mich haben wie das Bild mit zufälligem Rauschen.

Im Wesentlichen ist die Idee der Entropie so etwas wie "Anzahl der Mikrozustände, die mit dem Makrozustand übereinstimmen".

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

$h$$I$

funktioniert NICHT in der Praxis, aus dem einfachen Grund, dass es fast unmöglich ist, Pk zu bestimmen. Sie denken, dass Sie es schaffen, indem Sie die Anzahl der Graustufen berücksichtigen. Pk ist das nicht. Pk ist alle möglichen Kombinationen von Graustufen. Sie müssen also einen mehrdimensionalen Wahrscheinlichkeitsbaum erstellen, der 1, 2, 3 ... Pixelkombinationen berücksichtigt. Wenn Sie Shannons Arbeit lesen, sehen Sie, dass er diese Berechnung für einfaches Englisch unter Berücksichtigung einer Baumtiefe von 3 Buchstaben durchführt. Ohne Computer wird es dann unhandlich.

Das haben Sie selbst mit Aussage 2 bewiesen. Deshalb liefert Ihre Entropieberechnung für beide Bilder den gleichen Entropiestand, obwohl eines eindeutig weniger geordnet ist als das andere.

Es gibt auch kein solches Konzept der räumlichen Verteilung innerhalb der Entropieberechnung. Wenn ja, müssten Sie die Entropie für zeitlich verteilte Stichproben auch anders berechnen. Und was würden Sie für ein 11-dimensionales Datenarray tun? Zur Informationsentropie; es wird in Bytes gemessen.

Komprimieren Sie die Bilder einfach mit einem Komprimierungsalgorithmus. Es wird eine Schätzung der Entropie in Bytes ausgegeben. Dies geschieht für jedes Bild oder buchstäblich für alles, was digitalisiert werden kann, wie Musik oder Shakespeare-Stücke.

So. Ihr zufälliges Bild enthält ungefähr 114 KB, und Ihr bestelltes Bild enthält ungefähr 2,2 KB. Dies ist, was Sie erwarten würden, aber Sie wussten dies bereits, weil Sie sahen, dass die Bilddateigrößen von dieser Größe waren. Ich habe die komprimierte Größe um 33% reduziert, um zukünftige Verbesserungen der Komprimierungsalgorithmen zu ermöglichen. Ich kann nicht sehen, dass sie sich darüber hinaus verbessern, da die Verbesserungskurve zu einem wahren zugrunde liegenden Wert asymptotisch wird.

PS Aus Interesse hat Shakespeare in seinem gesamten Lebenswerk nur 1 MByte Entropie erzeugt, die mit dieser Technik berechnet wurde. Das meiste ist aber ganz gut.