Was ist die Grenze für verlustfreie Komprimierungsdaten? (wenn es eine solche Grenze gibt)

In letzter Zeit habe ich mich mit Komprimierungsalgorithmen befasst und mich gefragt, welches die beste Komprimierungsrate ist, die durch verlustfreie Datenkomprimierung erreicht werden kann.

Bisher war die einzige Quelle, die ich zu diesem Thema finden konnte, die Wikipedia:

Die verlustfreie Komprimierung von digitalisierten Daten wie Video, digitalisiertem Film und Audio bewahrt alle Informationen, kann jedoch aufgrund der intrinsischen Entropie der Daten selten viel besser als die 1: 2-Komprimierung sein .

Leider enthält der Wikipedia-Artikel keinen Verweis oder Verweis, um diese Behauptung zu stützen. Ich bin kein Experte für Datenkomprimierung, daher würde ich mich über alle Informationen freuen, die Sie zu diesem Thema bereitstellen können, oder wenn Sie mich auf eine zuverlässigere Quelle als Wikipedia verweisen könnten.

Ich bin mir nicht sicher, ob jemand erklärt hat, warum die magische Zahl genau 1: 2 zu sein scheint und nicht zum Beispiel 1: 1,1 oder 1:20.

Ein Grund ist, dass in vielen typischen Fällen fast die Hälfte der digitalisierten Daten Rauschen ist und Rauschen (per Definition) nicht komprimiert werden kann.

Ich habe ein sehr einfaches Experiment gemacht:

• Ich habe eine graue Karte genommen . Für ein menschliches Auge sieht es aus wie ein einfaches, neutrales Stück grauer Pappe. Insbesondere liegen keine Informationen vor .

• Und dann habe ich einen normalen Scanner genommen - genau die Art von Gerät, mit der die Leute ihre Fotos digitalisieren könnten.

• Ich habe die graue Karte gescannt. (Eigentlich habe ich die graue Karte zusammen mit einer Postkarte gescannt. Die Postkarte diente der Überprüfung der Gesundheit, um sicherzustellen, dass die Scannersoftware nichts Ungewöhnliches tut, z. B. automatisch Kontrast hinzufügen, wenn sie die nichtssagende graue Karte sieht.)

• Ich habe einen 1000x1000 Pixel großen Teil der Graukarte zugeschnitten und in Graustufen umgewandelt (8 Bit pro Pixel).

Was wir jetzt haben, sollte ein ziemlich gutes Beispiel dafür sein, was passiert, wenn Sie einen nichtssagenden Teil eines gescannten Schwarzweiß-Fotos untersuchen , zum Beispiel klaren Himmel. Grundsätzlich sollte es genau nichts zu sehen geben.

Bei einer größeren Vergrößerung sieht es jedoch tatsächlich so aus:

Es gibt kein deutlich sichtbares Muster, aber es hat keine einheitliche graue Farbe. Ein Teil davon wird höchstwahrscheinlich durch die Unvollkommenheiten der Graukarte verursacht, aber ich würde annehmen, dass das meiste davon einfach vom Scanner erzeugtes Rauschen ist (thermisches Rauschen in der Sensorzelle, dem Verstärker, dem A / D-Wandler usw.). Sieht ziemlich nach Gaußschem Rauschen aus. Hier ist das Histogramm (in logarithmischer Skala):

Wenn wir nun annehmen, dass jeder Pixel seinen Schatten aus dieser Verteilung ausgewählt hat, wie viel Entropie haben wir dann? Mein Python-Skript hat mir gesagt, dass wir bis zu 3,3 Bit Entropie pro Pixel haben . Und das ist viel Lärm.

Wenn dies wirklich der Fall wäre, würde dies bedeuten, dass die 1000 × 1000-Pixel-Bitmap, egal welchen Komprimierungsalgorithmus wir verwenden, im besten Fall in eine 412500-Byte-Datei komprimiert wird. Und was passiert in der Praxis: Ich habe eine 432018-Byte-PNG-Datei, ziemlich nah.

Wenn wir ein wenig über generalisieren, scheint es, dass ich unabhängig davon, welche Schwarzweißfotos ich mit diesem Scanner scanne, die Summe der folgenden Werte erhalte:

• "nützliche" Informationen (falls vorhanden),
• Lärm, ca. 3 Bits pro Pixel.

Selbst wenn Ihr Komprimierungsalgorithmus die nützlichen Informationen in << 1 Bit pro Pixel komprimiert, haben Sie immer noch bis zu 3 Bit pro Pixel inkomprimierbares Rauschen. Und die unkomprimierte Version ist 8 Bit pro Pixel. Das Kompressionsverhältnis liegt also im Bereich von 1: 2, egal was Sie tun.

Ein weiteres Beispiel mit dem Versuch, überidealisierte Bedingungen zu finden:

• Eine moderne DSLR-Kamera mit der niedrigsten Empfindlichkeitseinstellung (geringstes Rauschen).
• Eine unscharfe Aufnahme einer Graukarte (selbst wenn die Graukarte sichtbare Informationen enthält, werden diese verwischt).
• Konvertierung der RAW-Datei in ein 8-Bit-Graustufenbild ohne Kontrast. Ich habe typische Einstellungen in einem kommerziellen RAW-Konverter verwendet. Der Konverter versucht standardmäßig, das Rauschen zu reduzieren. Außerdem speichern wir das Endergebnis als 8-Bit-Datei - wir werfen im Wesentlichen die niedrigstwertigen Bits der rohen Sensorwerte weg !

Und was war das Endergebnis? Es sieht viel besser aus als das, was ich vom Scanner bekommen habe. Das Geräusch ist weniger ausgeprägt und es ist genau nichts zu sehen. Trotzdem ist das Gaußsche Rauschen da:

Und die Entropie? 2,7 Bit pro Pixel . Dateigröße in der Praxis? 344923 Bytes für 1M Pixel. Im besten Fall haben wir die Komprimierungsrate mit einigem Betrug auf 1: 3 erhöht.

Natürlich hat all dies nichts mit TCS-Forschung zu tun, aber ich denke, es ist gut zu bedenken, was die Komprimierung von digitalisierten Daten in der realen Welt wirklich einschränkt. Fortschritte bei der Entwicklung ausgefeilterer Komprimierungsalgorithmen und der CPU-Rohleistung werden nicht helfen. Wenn Sie das Rauschen verlustfrei speichern möchten, können Sie nicht viel besser als 1: 2.

Wissen Sie bereits über Shannons Satz der rauschfreien Codierung Bescheid ? Dieser Satz legt theoretische Grenzen für die verlustfreie Komprimierung fest. Einige der Kommentare der anderen scheinen davon auszugehen, dass Sie über dieses Theorem Bescheid wissen, aber aufgrund der Frage denke ich, dass es die Antwort sein könnte, nach der Sie suchen.

$n>0$

1. $n$

2. Die übliche praktische Lösung ist die Verwendung von 8 Bit, wenn die einzigen Ganzzahlen, die Sie jemals codieren werden, alle zwischen 1 und 256 liegen (verallgemeinern Sie dies auf 16, 32 und 64 Bit, wenn Sie möchten).

3. $n+1$$n$$n$ , desto kleiner ist die Größe der unären Codierung.

4. $\lceil\log_2 n\rceil$$\lceil\log_2 n\rceil+1$$n$$\lceil\log_2 n\rceil-1$$\lceil\log_2 n\rceil$$2\lceil\log_2 n\rceil-1$$n$$\lg n=\max(1,\lceil\log_2 n\rceil)$

5. $2\lceil\log_2 n\rceil-1$ Bits innerhalb eines , was in der Praxis angesichts der Komplexität besserer Lösungen am ehesten ausreicht.

6. $K$$K$ist nicht berechenbar. Eine einfache Umgehung dieses Begriffs bietet Levin bieten selbstbegrenzende Programme, bei denen Sie nur Programme mit einer begrenzten Ausführungszeit berücksichtigen (z. B. innerhalb eines konstanten Faktors der Länge der ursprünglichen Instanz, bei der es sich um eine Untergrenze für die Komplexität des Algorithmus, der jedes Symbol schreiben muss).

Es gibt eine ganze Community, die sich mit der Komplexität und den Varianten von Kolmogorov befasst, und eine andere Community, die an verlustfreier Komprimierung arbeitet (das Beispiel für Ganzzahlen, das ich verwendet habe, hat Entsprechungen für viele andere Datentypen), ich habe die Oberfläche kaum zerkratzt, und andere haben möglicherweise Präzisierungen hinzugefügt (Kolmogorov ist wirklich nicht meine Spezialität), aber ich hoffe, dass dies Ihnen hilft, Ihre Frage zu klären, wenn Sie nicht unbedingt die Antwort geben, auf die Sie gehofft haben :)

(nur eine Erweiterung meines Kommentars)

(Wie von Joe in seiner Antwort hervorgehoben) Shannon - in seiner Arbeit von 1948, " A Mathematical Theory of Communication formulierte " die Theorie der Datenkomprimierung und stellte fest, dass es eine grundlegende Grenze für die verlustfreie Datenkomprimierung gibt. Diese Grenze, die als Entropierate bezeichnet wird, wird mit H bezeichnet. Der genaue Wert von H hängt von der Informationsquelle ab, genauer gesagt von der statistischen Natur der Quelle. Es ist möglich, die Quelle mit einer Kompressionsrate nahe H verlustfrei zu komprimieren. Es ist mathematisch unmöglich, eine bessere Kompressionsrate als H zu erzielen.

Einige Bildklassen (z. B. medizinische Graustufenbilder) ohne kontrastreiche Kanten und mit glatten Pegelübergängen können jedoch komprimiert werden (nicht so effizient).

JPEG-LS und JPEG2000 scheinen die Standards für die verlustfreie Speicherung von medizinischen Bildern zu sein. In dieser Tabelle finden Sie einen Vergleich der Kompressionsverhältnisse (der JPEG-LS erzielt eine etwas bessere Komprimierung).

Bei der Verwendung der "verlustfreien medizinischen Bildkomprimierung" habe ich die folgenden Artikel gefunden, die Ihnen möglicherweise helfen:

Eine aktuelle (2011) Umfrage zu medizinischen Bildkomprimierungstechniken: Zweidimensionale medizinische Bildkomprimierungstechniken - Eine Umfrage

... Dieser Artikel bietet einen Überblick über verschiedene Komprimierungstechniken basierend auf DCT, DWT, ROI und neuronalen Netzen für zweidimensionale (2D) medizinische Bilder.

Detaillierte Darstellung von zwei verlustfreien Standardkomprimierungsalgorithmen: JPEG-LS und JPG2000 im verlustfreien Modus: Verlustfreie Komprimierung von medizinischen Graustufenbildern - Wirksamkeit traditioneller und moderner Ansätze

Es wurden dreitausendsechshundertneunundsiebzig (3.679) Einzelbild-Graustufenbilder aus mehreren anatomischen Regionen, Modalitäten und Anbietern getestet. ...

Eine weitere Umfrage: Eine Umfrage zu modernen medizinischen Bildkompressionstechniken

BEARBEITEN

Vielleicht fragen Sie sich immer noch: "Was zur Hölle ist die Entropie eines Bildes?" ... OK, es ist die Menge an Informationen, die im Bild enthalten sind ... Um es besser zu verstehen, sollten Sie etwas über die drei Phasen lesen, die normalerweise bei der Bildkomprimierung verwendet werden :

• Transformation (zum Beispiel Diskrete Wavelet-Transformation)
• Quantisierung
• Entropie-Codierung

Mit Google können Sie nach einem Lernprogramm oder Buch zur Bildkomprimierung suchen (z. B. nach einem kurzen Lernprogramm ) oder versuchen, ein technisches Online-Video anzusehen (z. B. Vorlesung 16 - Einführung in die Bild- und Videokodierung ).

Stellen Sie sich eine Datei als Zeichenfolge vor.

Sie können niemals bessere Ergebnisse erzielen als die Kolmogorov-Komplexität einer Zeichenfolge (dies entspricht der Definition der Komogorov-Komplexität).

Fixiere eine Stringlänge. Wir betrachten also nur Strings der Länge n.

Die Hälfte aller solcher Zeichenfolgen kann um höchstens 1 Bit komprimiert werden. 1/4 aller Strings können mit maximal 2 Bit komprimiert werden. 1/8 aller solcher Zeichenketten können um höchstens 3 Bits komprimiert werden.

Welcher Teil der Zeichenfolgen (Bilder, Dateien usw.) kann also im Verhältnis 2: 1 komprimiert werden - sehr, sehr wenige. Warum funktioniert die Komprimierung überhaupt? Da fast alle Daten, die echte Personen tatsächlich zu komprimieren versuchen, stark strukturiert sind, sieht es nicht wie eine zufällige Datei aus. Je zufälliger die Daten aussehen, desto schwerer zu komprimieren. Sie gehen Hand in Hand. Die meisten Saiten sehen zufällig aus.

Um dies in Aktion zu sehen, generieren Sie eine zufällige Datei mit einem zufälligen Prozess. Ich meine eine wirklich, wirklich zufällige Datei. Versuchen Sie nun, es mit Ihrem bevorzugten Komprimierungsalgorithmus zu komprimieren. Es bleibt entweder gleich groß oder wird fast die ganze Zeit größer.

Auf der Rückseite befinden sich stark komprimierbare Saiten. Nehmen Sie die folgende Zeichenfolge: 100000..000 (1 gefolgt von einer Million Nullen). Die Beschreibung davon passt in den vorhergehenden Satz, und ein Computer könnte es aus dieser Beschreibung rekonstruieren (oder eine sehr ähnliche). Diese Beschreibung ist jedoch nicht annähernd eine Million Stellen lang.

Tatsache ist, dass Saiten mit dieser Eigenschaft (stark komprimierbar zu sein) unter allen möglichen Saiten äußerst selten sind. Die sekundäre Tatsache ist, dass fast alle von Menschen erzeugten Daten super, super komprimierbar sind, weil sie so strukturiert sind.