Contest: Verlustfreie Kompression eines Rauschbildes

[Spasstiger]

Ich hab ein Bild mit einer Größe von 1024*1024 Pixeln erstellt, wobei jedes Pixel eine andere, zufällige Farbe hat. Es sind im Bild also auch 1024*1024=1048576 Farben enthalten.
Der theoretische Informationsgehalt des Bildes liegt bei 2.621.440 Byte = 2,5 MiB (20 Bit pro Pixel), gespeichert als BMP ist es 3.145.782 Byte (~3 MiB) groß.

http://www.abload.de/thumb/rgb_killernoise_10246ec.bmp (http://www.abload.de/image.php?img=rgb_killernoise_10246ec.bmp)

Eure Aufgabe: Ihr sollt das Bild verlustfrei möglichst klein bekommen. Ob ihr dazu ein Bildformat, ein Packprogramm oder was Selbstgeschriebenes verwendet, ist egal. Es soll nachher nur gewährleistet sein, dass das Orignalbild verlustfrei wiederhergestellt werden kann.
Ich persönlich halte es für unmöglich, die theoretische Grenzen von den 2,5 MiB zu unterschreiten, weil es sich halt beim Bild um ein Rauschen ohne irgendeine markante Struktur handelt. Ich lasse mich aber gern eines Besseren belehren.

Ich tu mir sogar schwer, das Bild unter 3 MiB zu bringen. Mir gelingt es weder mit dem PNG-Format, noch mit 7-Zip.

[looking glass]

Mhhh, ich hab gedacht, hey probier doch mal uharc, aber bin beim suchen der letzten Version bei der englischen Wikipedia über das hier gestolpert:

http://www.maximumcompression.com/data/bmp.php

Und bis auf StUFFIT (Platz 2) kenne ich dann keinen einzigen (bis dann auf Platz 23 7Zip auftaucht). Ich würde es ausprobieren, aber die neueste Sharewareversion finde ich irgendwie nur mit Anmeldungsgeblarre auf der Herstellerseite.

[Gast]

und wo ist das bild?

[looking glass]

Na oben verlinkt, klick auf das kleine Bild und das große wird angezeigt, speichern unter - fertig.

[_DrillSarge]I[]

http://files.filefront.com/rgb+killernoise+10246ec7z/;9990477;/fileinfo.html
.ecw-format als.7z gepackt -> 876kb

ecw ist zwar verlustbehaftet, aber ned hier, schaut selber
-> öffnen mit zB irfanview
€: die fraben sind leicht anders...k.a. warum, die farbtiefe ist dieselbe; verdammt

[Spasstiger]

I[;6424719']
ecw ist zwar verlustbehaftet, aber ned hier, schaut selber
-> öffnen mit zB irfanview
€: die fraben sind leicht anders...k.a. warum, die farbtiefe ist dieselbe; verdammt
Es gibt auch klare Kompressionsfehler. Überlagere einfach mal dein Bild mit dem Originalbild subtraktiv. ;)
Ich hab mir das nochmal überlegt. Weniger als 2,5 MiB = 2.621.440 Byte sind tatsächlich unmöglich. Der theoretische Informationsgehalt kann nicht unterschritten werden, wenn man verlustfrei komprimiert.

[_DrillSarge]I[]

Es gibt auch klare Kompressionsfehler. Überlagere einfach mal dein Bild mit dem Originalbild subtraktiv. ;)
yupp. hab irgendwas falsch eingestellt. muss mal schauen
-> ok, die sau hat sich paar tausend farbstufen gespart

[Spasstiger]

I[;6424738']yupp. hab irgendwas falsch eingestellt. muss mal schauen
-> ok, die sau hat sich paar tausend farbstufen gespart
Nicht nur das, die Farben sind auch bei jedem einzelnen Pixel falsch.
Wenns nur drum, irgendein beliebiges Rauschbild zu speichern: Das bekomm ich mit wenigen Bytes hin. ;)

[_DrillSarge]I[]

Nicht nur das, die Farben sind auch bei jedem einzelnen Pixel falsch.
Wenns nur drum, irgendein beliebiges Rauschbild zu speichern: Das bekomm ich mit wenigen Bytes hin. ;)
eben, das ding hat sich auf nen farbraum beschränkt und dann dort die farben angenähert

[_DrillSarge]I[]

Ich tu mir sogar schwer, das Bild unter 3 MiB zu bringen. Mir gelingt es weder mit dem PNG-Format, noch mit 7-Zip.
jpeg2000 schafft es verlustfrei auf 2.99mb (3.145.529 Bytes) ;D

[Gast]

Na oben verlinkt, klick auf das kleine Bild und das große wird angezeigt, speichern unter - fertig.

hm, das thumb funktioniert bei mir nicht, deshalb seh ich auch keinen link (der aber komischerweise funktioniert)

[rotalever]

Es gibt auch klare Kompressionsfehler. Überlagere einfach mal dein Bild mit dem Originalbild subtraktiv. ;)
Ich hab mir das nochmal überlegt. Weniger als 2,5 MiB = 2.621.440 Byte sind tatsächlich unmöglich. Der theoretische Informationsgehalt kann nicht unterschritten werden, wenn man verlustfrei komprimiert.
Man könnte höchstens einen Maßgeschneiderten Algorithmus nehmen, der das Bild neu generiert, da die Zufallszahlen ja vermutlich aus einem Generator stammen. Dieser Algorithmus ist natürlich nur ein paar kb groß:rolleyes:

[Momo]

.rle --> .7z --> 0,99mb (1.044.653 Bytes)

http://rapidshare.com/files/106710307/rgb_killernoise_10246ec.7z.html

[MrMostar]

Auch paq8o9 beisst sich daran die Zähne aus:


killernoise_10246ec.bmp 3145782 -> BMP 1024x1024 3147985
3145782 -> 3148035
Time 75.75 sec, used 234051935 bytes of memory

Close this window or press ENTER to continue...


ps. dein bildlink ist bei mir unsichtbar, ich musste ihn aus der Pagesource rausfriekeln:
www.abload.de/image.php?img=rgb_killernoise_10246ec.bmp

[Spasstiger]

.rle --> .7z --> 0,99mb (1.044.653 Bytes)

http://rapidshare.com/files/106710307/rgb_killernoise_10246ec.7z.html
Das Bild hat nur 256 Farben. Aber dafür ist es doch recht effizient codiert.
PNG verwendet übrigens auch eine Lauflängencodierung (wie RLE = run length encoding).

Ich bin inzwischen auf eine Methode gekommen, wie man exakt das gegebene Bild mit weniger als 2,5 MiB speichern kann. Und zwar benötigt man das Vorwissen, das beim Zielbild jedes Pixel eine andere Farbe hat. Für solche Bilder gibt es (1024^2)! Möglichkeiten, jede Möglichkeit hat also den Informationsgehalt von log2((1024^2)!) Bits. Das sind ca. 2,32 MiB. :)

P.S.: Wenn ihr die Rechnung von log2((1024^2)!) in endlicher Zeit rechnen wollt, rechnet lieber sum(log2(x), x=1..1024^2). Das geht um einige Größenordnungen schneller. ;)

Man könnte höchstens einen Maßgeschneiderten Algorithmus nehmen, der das Bild neu generiert, da die Zufallszahlen ja vermutlich aus einem Generator stammen. Dieser Algorithmus ist natürlich nur ein paar kb groß:rolleyes:
Mit ein paar kb kommst du da nicht hin. Meine Idee oben verfolgt ja genau den Ansatz, ein Generator für Rauschbilder, in dem kein Pixel dieselbe Farbe hat. Zur Speicherung des Programmparameters ("Rauschbild Nr. xyz soll erzeugt werden") braucht man aber 2,32 MiB. Eine noch effizientere Lösung fällt mir momentan nicht ein. Um den Parameter für das obige Bild zu ermitteln, müsste man noch einen Rückwärtsgenerator programmieren, der genau das umgekehrte wie der Rauschbildgenerator macht.

[looking glass]

Grins, auch BMP kann RLE verwenden (limitiert auf 4/8Bit), hab es ausprobiert, wird dadurch auch nicht kleiner.

Hab noch eine alte STUFFIT Version (9.5) ohne Regzwang gefunden, hab sowohl BMP, als auch Jpeg2000 lossless probiert, wirklich kleiner wurde das nicht, unter 3MB bin ich so nicht gekommen.

Bei deiner Methode, stimmte dann die Lage von Pixel Y mit Farbwert X auch überein? Mag zwar dumm sein, aber mit der Methode bekommst Du doch nur alle Farben ins Bild, nicht jedoch ihre exakte Lage, oder?

[Spasstiger]

Bei deiner Methode, stimmte dann die Lage von Pixel Y mit Farbwert X auch überein? Mag zwar dumm sein, aber mit der Methode bekommst Du doch nur alle Farben ins Bild, nicht jedoch ihre exakte Lage, oder?
Der Generator wählt aus 1024^2 möglichen Rauschbildern, wo die Lage jedes Pixels exakt vorgegeben ist. Welche Farben genau verwendet werden können, müsste man zunächst aus dem Vorlagenbild ermitteln und im Algorithmus ablegen. Der Algorithmus wird dabei natürlich etwas voluminös, was den Zweck des Ganzen ad absurdum führt. Denn dann könnte man auch gleich das ganze Bild im Generator ablegen. ;)
Eigentlich sollte man den Speicherverbrauch des Algorithmus auch mit in den Speicherverbrauch für das Bild einbeziehen. Bestehen in der Hinsicht große Unterschiede zwischen BMP, JPG, RLE, 7-Zip, etc.?

[rotalever]

Mit ein paar kb kommst du da nicht hin. Meine Idee oben verfolgt ja genau den Ansatz, ein Generator für Rauschbilder, in dem kein Pixel dieselbe Farbe hat. Zur Speicherung des Programmparameters ("Rauschbild Nr. xyz soll erzeugt werden") braucht man aber 2,32 MiB. Eine noch effizientere Lösung fällt mir momentan nicht ein. Um den Parameter für das obige Bild zu ermitteln, müsste man noch einen Rückwärtsgenerator programmieren, der genau das umgekehrte wie der Rauschbildgenerator macht.
Wie hast du denn die Zufallszahlen erzeugt? Echte Zufallszahlen? Dann stimmt es wohl. Sind es aber Zahlen aus einer normalen Bibliothek, zum Beispiel in C einfach rand() dann ist die einzige Information die man braucht die Initialisierung des Generators und halt einen kleinen Algorithmus.

[looking glass]

Das wäre ja geschummelt, nee, nee...

[Spasstiger]

Wie hast du denn die Zufallszahlen erzeugt? Echte Zufallszahlen? Dann stimmt es wohl. Sind es aber Zahlen aus einer normalen Bibliothek, zum Beispiel in C einfach rand() dann ist die einzige Information die man braucht die Initialisierung des Generators und halt einen kleinen Algorithmus.
Ich hab in Matlab einen Vektor mit Zahlen von 1 bis 2^24 erzeugt, welche die Farben repräsentieren. Anschließend hab ich den Vektor zufällig permutiert und als Bild mit 4096*4096 Pixeln gespeichert. Dann hab ich nur noch einen 1024*1024 Pixel großen Ausschnitt davon genommen und hochgeladen. ;)

Ich hab eben noch ausgerechnet, dass man zur Speicherung der möglichen Farben bei meinem oben vorgeschlagenen Rauschbildgenerator rund 2,99 MiB benötigt (könnte man mit einem zusätzlichen Algorithmus noch weiter komprimieren, aber nicht unter 2,5 MiB). D.h. 2,32 MiB für die Quasi-Positionsdaten, 2,99 MiB für die Farbdaten und ein paar kB für den eigentlichen Code. D.h. rund 5,32 MiB für das gesamte Bild. Irgendwo doch nicht so toll. Ich glaube, dass da sogar BMP effizienter ist, der Algorithmus selbst dürfte dort nur wenige kB benötigen.
Wäre das Bild 4096*4096 Pixel groß und würde damit alle möglichen 2^24 Farben verwenden, wäre mein obiger Algorithmus aber durchaus sehr effizient, da man dann keine Informationen zur Farbpalette mehr speichern muss.

[rotalever]

Ich hab in Matlab einen Vektor mit Zahlen von 1 bis 2^24 erzeugt, welche die Farben repräsentieren. Anschließend hab ich den Vektor zufällig permutiert und als Bild mit 4096*4096 Pixeln gespeichert. Dann hab ich nur noch einen 1024*1024 Pixel großen Ausschnitt davon genommen und hochgeladen. ;)

Erzeugen des Vektors mit Zahlen: Konstante Daten für Algorithmus, wenige kb
Zufällig Permutation: Konstante Daten für Algorithmus, wenige kb + initialisierung eines Zufallsgenerators (i.d.R. ein paar byte)
Wählen eines Ausschnitts? Wie wurde der gewählt? Auch "zufällig" vom Programm? Wie auch immer, es gibt dafür rund 9437184 Möglichkeiten, man speichert also eine Zahl von 0~9437184, wenige byte.

Alles in allem sind das wenige Kilobyte, da Zufallsgeneratoren bei vorgegebener Initialisierung (i.d.R.) deterministisch sind. (Es sei denn du hast die Zahlen echt erzeugt, daran glaube ich jetzt mal nicht ;))

Natürlich, ein wenig geschummelt ist es schon, da es sich um eine spezielle Kompression nur für Bilder dieser Art handelt, aber funktionieren tut es X-D.

Ich hab eben noch ausgerechnet, dass man zur Speicherung der möglichen Farben bei meinem oben vorgeschlagenen Rauschbildgenerator rund 2,99 MiB benötigt. D.h. 2,32 MiB für die Quasi-Positionsdaten, 2,99 MiB für die Farbdaten und ein paar kB für den eigentlichen Code. D.h. rund 5,32 MiB für das gesamte Bild. Irgendwo doch nicht so toll.
Versteh ich nicht, wieso sollte man soviel speichern?

[Spasstiger]

Erzeugen des Vektors mit Zahlen: Konstante Daten für Algorithmus, wenige kb
Zufällig Permutation: Konstante Daten für Algorithmus, wenige kb + initialisierung eines Zufallsgenerators (i.d.R. ein paar byte)
Wählen eines Ausschnitts? Wie wurde der gewählt? Auch "zufällig" vom Programm? Wie auch immer, es gibt dafür rund 9437184 Möglichkeiten, man speichert also eine Zahl von 0~9437184, wenige byte.
Es gibt für die Erzeugung eines 4096*4096-Bildes, wo sich keine Farbe wiederholt, (4096*4096)! Möglichkeiten. Der Parameter hat also log2((4096^2)!) Bits = 45,11.. MiB. Nicht sehr effizient, wenn man letztlich nur 1024*1024 Pixel benötigt.

Versteh ich nicht, wieso sollte man soviel speichern?
Das wäre für den Fall, dass man die Farbpalette mitspeichert. Man weiß ja nicht genau, welche 2^20 von den 2^24 möglichen Farben tatsächlich verwendet werden.

Letzlich ist es wohl doch nicht möglich, die gegebene Bildinformation mit weniger als 2,5 MiB zu speichern, wenn man auch den Speicherbedarf des Decodierers mit einbezieht.

[looking glass]

Nicht möglich, so sicher wäre ich mir da nicht, wer weiß schon was die Zukunft bringt, heutzutage nicht möglich, das leider ja.

[Trap]

Letzlich ist es wohl doch nicht möglich, die gegebene Bildinformation mit weniger als 2,5 MiB zu speichern, wenn man auch den Speicherbedarf des Decodierers mit einbezieht.
Wenn es Pseudozufallszahlen sind (wenn du keine Quelle für echte Zufallszahlen benutzt hast, sind es Pseudozufallszahlen), reicht der Startwert des Zufallszahlengenerators + ein ein paar kB Algorithmus.

Wenn es echte Zufallszahlen sind, ist es immernoch möglich eine kürzere Beschreibung für genau das Bild zu finden (werde ich aber nicht versuchen), aber nicht allgemein für alle so erzeugten Bilder.
Komprimierung von Zufallsdaten heißt nämlich auch, dass man das Ergebnis direkt wieder komprimieren kann und damit bekommt man jede Datei beliebig klein ;)

[Spasstiger]

Wenn es Pseudozufallszahlen sind (wenn du keine Quelle für echte Zufallszahlen benutzt hast, sind es Pseudozufallszahlen), reicht der Startwert des Zufallszahlengenerators + ein ein paar kB Algorithmus.
Es sind wohl Pseudozufallszahlen. Ich habe eine Zufallspermutation (randperm.m) erzeugen lassen, das ist eine in Matlab integrierte Funktion. Diese setzt jedoch wiederum auf einen Pseudozufallszahlengenerator (rand.m) auf Basis des Mersenne-Twister-Algorithmus.

/EDIT: Der Mersenne-Twister-Pseudozufallszahlengenerator hat eine Periodenlänge von 2^19937-1 . D.h. man kan den Startwert in 19937 Bits speichern. Das bedeutet ja doch eine erhebliche Einsparung.

[rotalever]

Davon rede ich ja die ganze Zeit. :confused::confused::confused:

Dein Bild ist halt nicht wirklich zufällig, sondern nur Pseudozufällig. Deshalb versagen normale Kompressionsalgorithmen, aber dadurch das es nicht echt zufällig ist, kann ich, wie schon gesagt, das ganze mit wenigen kb komprimieren.

Durch Verwendung von nicht echten Zufallszahlen sinkt eben einfach der Informationsgehalt, da im Endeffekt nur die Initialisierung des Generators zum erstellen des Bildes bekannt sein muss.

[Spasstiger]

Davon rede ich ja die ganze Zeit. :confused::confused::confused:
Ja, sorry, hab dich zuerst nicht richtig verstanden.

Btw. hier noch ein Bild, diesmal mit 2^24 Farben.

http://www.abload.de/thumb/rgb_completetnk.png (http://www.abload.de/image.php?img=rgb_completetnk.png)
Direktlink: http://www.abload.de/img/rgb_completetnk.png

Die Auflösung ist 16384*16384, so dass jede Farbe von 4*4 Pixeln repräsentiert wird. Das Bild hab ich eigentlich erstellt, um eventuell auftretendes Colorbanding beim Monitor zu prüfen, um also zu schauen, wie gut der Monitor und seine Einstellungen auf das eigene Farbempfinden optimiert sind.

Aber man kann es auch ganz nett für Kompressionstests verwenden. Mit 7-Zip komm ich immerhin auf 7 kB.