Forum: PC-Programmierung Huffman-Kodierung, typische Tabellengrößen


von Stephan (Gast)


Lesenswert?

Ich versuche grad die typische Größe eines Huffman-Baumes (nach 
optimaler Kodierung) abzuschätzen. Finde aber auf die schnelle keine 
verwertbaren Infos.

Wertebereich: 0 - 2^16-1
im wesentlichen genutzt: 1024-1080
Zahl der Werte: 250-16.000 (abhängig von der Größe)

Geht darum ob vorgegebene oder individuelle Tabellen zum Einsatz kommen, 
ob die Daten in Blöcke aufgeteilt werden und wie groß die Blöcke mit 
individuellen Tabellen sinnvollerweise sind.

Falls jemand entsprechende Links/Erfahrungswerte auf Vorrat hat, bitte 
posten.

Schöne Grüße,
Stephan

von Vlad T. (vlad_tepesch)


Lesenswert?

Ich ferstehe nicht, was du mit "typischer Größe" eines Huffmanbaumes 
meinst.
der Baum ist immer gleich groß. für jedes Zeichen des Alphabets ein 
Knoten.
Die Frage ist nur, wie dieser angeordnet ist.

Oder meinst du die größe der komprimierten Daten?
wenn der Baum optimal ist, lässt sich das doch wunderbar berechnen.
Schau mal nach Entropie


Wenn ich mich recht erinnere gibt es für die Erzeugung von Huffmanbäumen 
folgende 2 prinzipielle Ansätze:

1) man geht komplett durch die Daten und zählt die Vorkomnisse der 
Zeichen , baut daraus einen optimalen Baum und kodiert in einem 2. 
Schritt die Daten mit diesem Baum und speichert den Baum mit den Daten 
ab

Dies ist natürlich nicht auf kontinuierliche Datenströme anwendbar, oder 
der komplette Strom muss gepuffert werden.
Dafür ist der Baum optimal.

2) die Dynamische Erzeugung des Baumes und on-the-fly codierung, während 
die Eingabezeichen sequenziell eingehen.
Hierbei braucht der Baum nicht extra gespeichert oder übertragen werden, 
da dieser sich automatisch ergibt. Allerdings ist am Anfang der 
Übertragung die Codierung nicht optimal, da die Häufigkeiten unbekannt 
sind.

Vorteil ist hier der geringe Arbeitsspeicherbedarf.


fest vorgegebene Tabellen machen daher nur Sinn, es sei denn man weiß 
sehr genau über die statistische Verteilung der Daten bescheid und man 
ist sich sicher, das diese sich auch nicht ändert.

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

Version 3) Die Verteilung ist bekannt und der Baum wird einmalig 
berechnet.

Wenn die Verteilung schwank, kann man auch eine Menge an Bäumen vorgeben 
und dann einfach über einen Index vorgeben welcher genutzt werden soll 
(wird bei MP3 mein ich so gemacht).

von Andreas F. (aferber)


Lesenswert?

Läubi .. schrieb:
> Wenn die Verteilung schwank, kann man auch eine Menge an Bäumen vorgeben
> und dann einfach über einen Index vorgeben welcher genutzt werden soll
> (wird bei MP3 mein ich so gemacht).

Yepp, MP3 hat 32 vordefinierte Bäume, aus denen auf Ebene von einzelnen 
Frames (also nicht der ganzen Datei) der beste ausgewählt wird.

Allerdings ist das auch ein Fall, wo man aufgrund der Eigenschaften von 
Musik im Allgemeinen und des psychoakustischen Modells im Speziellen 
ziemlich gute Vorhersagen über den Aufbau der zu kodierenden Daten 
machen kann. "Nur" der jeweils im Frame dominierende Frequenzbereich 
schwankt, weshalb man nicht mit nur einem Baum hinkommt.

Andreas

von Stephan (Gast)


Lesenswert?

Vlad Tepesch schrieb:
> der Baum ist immer gleich groß. für jedes Zeichen des Alphabets ein
> Knoten.
> Die Frage ist nur, wie dieser angeordnet ist.

Ich war davon ausgegangen, dass sich der Baum nochmal schlau 
komprimieren lässt...
Mindestens kann ich aber den Schwerpunktmäßig genutzten Wertebereich 
1024-1080 durch ne zusätzliche Kodierung ein wenig eindampfen.

Andreas Ferber schrieb:
> Yepp, MP3 hat 32 vordefinierte Bäume, aus denen auf Ebene von einzelnen
> Frames (also nicht der ganzen Datei) der beste ausgewählt wird.

Das ist schonmal ein starkes Pro für vordefinierte Tabellen.

Andererseits... Mit gemeinsammer Tabelle hab ich in meinen Beispieldaten 
(Fotos/RAW-Daten) 2MByte an Entropie (nach Wahrscheinlichkeiten) über 
alles. Aufgeteilt in 2500 Blöcke ist die Summe nur noch 1,3MByte.
Je Block kommen nach meinen Stichproben nur 8-100 Werte vor. Die Bäume 
dürften damit spielend in die eingesparten 700kByte passen.
Evtl. sind vordefinierte Tabellen aber nochmal effizienter.

Ich werd noch mehr Testen müssen...

Danke jedenfalls für den Input,
Stephan

von Vlad T. (vlad_tepesch)


Lesenswert?

versuchs doch mal die Daten als 8bit zu intepretieren, dann wird der 
Baum kleiner. vielleicht sogar das Endergebnis

Der Vorteil von individuellen Bäumen ist, dass der der Baum nur die 
benutzten Literale des Alphabets enthält.

wenn in einer Datei zB nur die Literale 0x01 und 0xff vorkommen, sind 
auch nur diese in dem Baum.
willst du hingegen den Baum auch für unbekannte Daten verwenden und bist 
nicht 100%ig sicher, dass andere Literale nicht auftreten können, müssen 
die natürlich auch einen Platz in dem Baum bekommen.

von Martin (Gast)


Lesenswert?

Wenn möglich poste bitte eine Beispielsdatei.

von Stephan (Gast)


Lesenswert?

Martin schrieb:
> Wenn möglich poste bitte eine Beispielsdatei.

Da werd ich noch ne Ecke dazu erklären müssen, sonst gibts nur unnütze 
Verwirrung. Geheimnis ists keines. Dauert aber ein wenig (ich komm grad 
immer nur Abends kurz dazu).

Im Endeffekt mag ich die RAW-Daten einer DSLR effizient (mit geringen, 
aber genau definierten Verlusten) ablegen. Je nach Wert und ISO lassen 
sich da so 2-8 Bit ohne weiteres entsorgen.
Nach meinen derzeitigen Ansätzen ist der Wertebereich zwar recht klein, 
für den allgemeinen Fall (ohne Verluste) sollte das ganze aber auch für 
aktuell 0-2^14 und mit ein wenig Reserve 0-2^16 funktionieren.

Jpeg2k verlustlos (Jasper) lässt sich für den Anwendungsfall vmtl. um 
10-20% übertreffen. Jpek2k verlustbehaftet (max. Qualität) ist gut, aber 
zu undefiniert und hat mir schon zu viele Artefakte.
Evtl. ist Jpeg2k verlustbehaftet und ein zusätzlicher Differenzdatensatz 
der beste Ansatz.

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

Für Bilder ist Huffman aber nicht so gut geeignet, Fotos vielleicht. 
Wieso nutzt du nicht einfach ZIP/PNG oder irgendwas das verlustfrei 
komprimiert und schon da ist?

von Andreas F. (aferber)


Lesenswert?

Läubi .. schrieb:
> Wieso nutzt du nicht einfach ZIP/PNG oder irgendwas das verlustfrei
> komprimiert und schon da ist?

Ack, und speziell bei PNG kann es helfen, einen PNG-Optimizer wie 
pngcrush (http://pmt.sourceforge.net/pngcrush/) oder OptiPNG 
(http://optipng.sourceforge.net/) auf das Bild anzuwenden. Häufig können 
die das Bild nochmal deutlich besser komprimieren als die Export-Filter 
von gängigen Bildbearbeitungsprogrammen.

Andreas

von Vlad T. (vlad_tepesch)


Lesenswert?

Läubi .. schrieb:
> Für Bilder ist Huffman aber nicht so gut geeignet, Fotos vielleicht.

eher umgedreht.

Fotos habe durch das Signalrauschen der ADCs eine recht hohe Entropie, 
was eine verlusstfreie Kompression erheblich erschwert.

Irgendwelche Grafiken oder Cliparts hingegen haben hingegen einfarbige 
Flächen, bzw nicht so viele verschiednene Farben, was eine 
Huffman-Kompression begünstigt.

von Stephan (Gast)


Lesenswert?

Vlad Tepesch schrieb:
> Fotos habe durch das Signalrauschen der ADCs eine recht hohe Entropie,
> was eine verlusstfreie Kompression erheblich erschwert.

Das für das Ergebnis unsinnige Rauschen (ADC, Schrotrauschen, etc.) will 
ich grade vorab durch sinnvolle Quantisierungsstufen eliminieren.
Aus 14 Bit ab Sensor bleiben da noch - je nach Verlustrate und ISO - 
zwischen 30 und 500 Werte übrig.

Läubi .. schrieb:
> Wieso nutzt du nicht einfach ZIP/PNG oder irgendwas das verlustfrei
> komprimiert und schon da ist?

Hatte ich keine guten Ergebnisse mit. Mit bz2 hatte ich die bei weitem 
besten Werte.
JP2K (verlustlos) ist in einem Szenario nochmals etwas besser, in 
anderen wiederum schlechter.

Andreas Ferber schrieb:
> speziell bei PNG kann es helfen, einen PNG-Optimizer wie
> pngcrush (http://pmt.sourceforge.net/pngcrush/) oder OptiPNG
> (http://optipng.sourceforge.net/) auf das Bild anzuwenden.

Probier ich aus.

von Vlad T. (vlad_tepesch)


Lesenswert?

Stephan schrieb:
> Das für das Ergebnis unsinnige Rauschen (ADC, Schrotrauschen, etc.) will
> ich grade vorab durch sinnvolle Quantisierungsstufen eliminieren.
> Aus 14 Bit ab Sensor bleiben da noch - je nach Verlustrate und ISO -
> zwischen 30 und 500 Werte übrig.

jetzt nenn doch mal endlich deinen Anwendungsfall.

Ich kann mir kaum einen Imager vorstellen, der zwar 14bit Auflösung hat, 
aber davon 5-9bit Rauschen sind.

Solte das wirklich der Fall sein, kannst du den 14bit wert ja auch 
getrost 6 Bits nach rechts schieben und hast einen 8bit Wert, dH du 
sparst schon mal so mindestens die Hälfte (ich geh mal davon aus, dass 
die 14bit in einem uint16 codiert sind) ohne nennenswerten 
Informationsverlust.

einige Sensoren haben Blacklines, die man auslesen kann.
Das sind Imagerzeilen, die nicht belichtet werden. aus diesen kann man 
recht bequem das thermische Rauschen ermitteln, was ohnehin auf jedem 
Pixel drauf ist.
Das gibt einen ein Gefühl für die Größenordnung des Bildrauschens.

von Stephan (Gast)


Lesenswert?

Vlad Tepesch schrieb:
> jetzt nenn doch mal endlich deinen Anwendungsfall.

Ich hatte eigentlich eher mit 2-3 schnellen Antworten mit ein paar Links 
gerechnet. Ich komm wie schon geschrieben nur gelegentlich zu dem 
Projekt.
Gedanklich gestartet ist das ganze hier: 
http://www.dslr-forum.de/showthread.php?t=496854&page=3 (untere Hälfte)

Damals hatte ich (bei sehr hohen ISOs) schon ne Kompression um Faktor 
2.5 erreicht, ohne signifikant Daten zu verlieren.
Das lässt sich aber sicher einiges verbessern. Die Daten sind halt 
einfach nicht mehr so verteilt wie - in dem Beispiel - DNG das erartet.

Ich mag:
- nicht relevante Daten in den Fotos entsorgen (offensichtliches 
Rauschen, Vorschaubilder)
- RAW-Format erhalten (Optionen hinsichtlich Weißabgleich, etc.)
- schnelle Vorschauen auf Basis der RAW-Daten ermöglichen

Meine damaligen Probleme die Daten zurückzukonverten und in nen normalen 
Workflow zu bringen sind inzwischen gelöst.
Vorschaubilder lassen sich auch auf Basis der RAW-Daten in 
nullkommanichts erzeugen (evtl. progressive Kodierung).

Vlad Tepesch schrieb:
> Ich kann mir kaum einen Imager vorstellen, der zwar 14bit Auflösung hat,
> aber davon 5-9bit Rauschen sind.

Doch.
Eine Canon 7D liefert bei ISO3200 zwar 14Bit ab. Im Abstand von 1 Sigma 
des Rauschpegels quantisiert verbleiben aber nur 64 Codes (evtl. noch 
ein paar nach oben/unten als Reserve dazu).
Beim Max-Wert sinds nur ca. 1.000 Elektronen die detektiert werden. Da 
ist auch ohne die Elektronik schon ein Schrotrauschen von +-32 
Elektronen drauf.

Vlad Tepesch schrieb:
> Solte das wirklich der Fall sein, kannst du den 14bit wert ja auch
> getrost 6 Bits nach rechts schieben und hast einen 8bit Wert

Geht so nicht, weil der Rauschanteil mit dem Wert ansteigt (etwa 
sqrt(BASENOISE^2+(a*value)^2)). Ist aber auch kein Problem.
Eher schon: das was rauskommt entspricht nicht mehr der Statistik 
normaler Fotos und die Kompressionsverfahren arbeiten schlecht(er).

Vlad Tepesch schrieb:
> einige Sensoren haben Blacklines, die man auslesen kann.

Ja. Ist aber eher was für (viel) später.

von Vlad T. (vlad_tepesch)


Lesenswert?

Stephan schrieb:
> Gedanklich gestartet ist das ganze hier:
> http://www.dslr-forum.de/showthread.php?t=496854&page=3 (untere Hälfte)

Da bin ich jetzt erlich gesagt zu faul mir das alles durchzulesen.
Was ich eigentlich meinte war aber auch, unter welchen Bedingungen du 
was fotografierst. (aber eher interessehalber)

was ich aber so rausgelesen habe, ist, dass scheinbar die RAW-Formate 
schon (verlustfrei) komprimiert sind.
ganz leicht zu erkennen sollte das an der Dateigröße sein.
ein unkomprimiertes RAW-Format sollte bei 18MP ja (je nach Codierung der 
14bit Werte und zusätzlich enthaltener Daten) 32-38MB groß sein.


Stephan schrieb:
> Doch.
> Eine Canon 7D liefert bei ISO3200 zwar 14Bit ab. Im Abstand von 1 Sigma
> des Rauschpegels quantisiert verbleiben aber nur 64 Codes (evtl. noch
> ein paar nach oben/unten als Reserve dazu).
> Beim Max-Wert sinds nur ca. 1.000 Elektronen die detektiert werden.
das heißt die unteren 4 bit kannst du auf jeden Fall entsorgen.

> Da ist auch ohne die Elektronik schon ein Schrotrauschen von +-32
> Elektronen drauf.
sind diese "64 Codes" denn gleichmäßig verteilt, oder gibt es da eine 
typische Kurve? Wenn du es schaffst deine Daten auf diese 64 Werte zu 
quantisieren, dann hast du ja schon gewonnen. Allerdings schreibst du 
bei deinen Anforderungen auch:
> - RAW-Format erhalten (Optionen hinsichtlich Weißabgleich, etc.)
Das heißt ja wiederum, du willst die Infos doch nicht wegwerfen.

Brauchst du denn diese hohe Auflösung?
Du könntest die Signale eventuell verbessern, wenn du mehrere Pixel zu 
einem zusammenfasst.
Im simpelsten Fall (bei linearer Kennline) einfach, indem du jeweils 4 
gleichfarbige Pixel aufaddierst.
1
b11 g11 b12 g12 b13 g13 b14 g14      
2
g21 r21 g22 r22 g32 r23 g24 r24
3
b31 g31 b32 g32 b33 g33 b34 g34
4
g41 r41 g42 r42 g42 r43 g44 r44
5
6
             |
7
             V
8
9
(b11+b12+b31+b32)  (g11+g12+g31+g32)  ...
10
(g21+g22+g41+g42)  (r21+r22+r41+r42)  ...


Stephan schrieb:
> Geht so nicht, weil der Rauschanteil mit dem Wert ansteigt (etwa
> sqrt(BASENOISE^2+(a*value)^2)).
Da sind meine Kenntniss zu begrenzt. Woher kommt das? und wo kommt der 
Basenoise her?
Jedes Pixel wird doch gleich lang belichtet (falls keine (pseudo)log. 
Kennline). Dh, das Rauschen wirkt doch auf alle gleich, natürlich mit 
individueller Streuung, die zu den bekannten bunten Pixeln führt.

Mit Hilfe der Blacklines kann man aber genau dieses Rauschen ermitteln.
dh.man kann die Bildpixel wenigstens um den Mittelwert des Rauschens 
bereinigen oder wenigstens abschätzen, ob mein Signal, was ich zu sehen 
glaube, wenigstens größer als Rausch-Mittelwert+(1..3)*Rausch-Sigma ist.

> Ist aber auch kein Problem.
> Eher schon: das was rauskommt entspricht nicht mehr der Statistik
> normaler Fotos und die Kompressionsverfahren arbeiten schlecht(er).

Das beste wäre, du postest einfach mal ein Beispiel-File, um der 
Ursprünglichen Problematik wieder etwas näher zu kommen.

Wobei mich das ganze grundsätzlich auch interessiert.
Prinzipiell hört sich das ganze aber für mich danach an, als wenn der 
Sensor für den Anwendungsfall nicht geeignet wäre.
Bei so lichtschwachen Szenarios wäre ein Monochromsensor wahrscheinlich 
sinnvoller, bei dem nicht schon mal eben 2/3 der einfallenden Energie in 
dem Filterpattern hängen bleibt.

von Stephan (Gast)


Lesenswert?

Vlad Tepesch schrieb:
> Da bin ich jetzt erlich gesagt zu faul mir das alles durchzulesen.

Das versteh ich (und habs nicht anders erwartet). Drum wollt ich nicht 
so weit ausholen, bzw. nach den Rückfragen versuchen das ganze auf einen 
knappen Abstract zu bringen.

Vlad Tepesch schrieb:
> Was ich eigentlich meinte war aber auch, unter welchen Bedingungen du
> was fotografierst. (aber eher interessehalber)

Nichts spezielles. Fotos halt. Canon 40D und 7D und der ganze 
ISO-Bereich.

Vlad Tepesch schrieb:
> was ich aber so rausgelesen habe, ist, dass scheinbar die RAW-Formate
> schon (verlustfrei) komprimiert sind.

Sind sie, aber nicht wirklich optimal. bz2 codiert die Rohdaten in 
meinem Testbild schon mit 7% weniger Platz.

Vlad Tepesch schrieb:
> das heißt die unteren 4 bit kannst du auf jeden Fall entsorgen.

Der Rest ist auch nicht so schwer. Die Kurve ist ja relativ genau 
bekannt.
Die 4 bit/64Werte gelten übrigens nur für die ISO3200. Bei ISO100 sinds 
eher 2,5bit/400Werte.
ISO-Wert ist bekannt, also entsprechend angepasste Kurven.

Vlad Tepesch schrieb:
> sind diese "64 Codes" denn gleichmäßig verteilt, oder gibt es da eine
> typische Kurve? Wenn du es schaffst deine Daten auf diese 64 Werte zu
> quantisieren, dann hast du ja schon gewonnen.

In der Grundtendenz ja (die untere Hälfte ist in der Regel deutlich 
stärker). Kann aber von Foto zu Foto schwanken.

>> - RAW-Format erhalten (Optionen hinsichtlich Weißabgleich, etc.)
> Das heißt ja wiederum, du willst die Infos doch nicht wegwerfen.

Ich will die Farbauszüge (Grün1+2, Rot, Blau) nicht zusammenwerfen 
(Bayer-Interpolation), weil damit sehr viele Möglichkeiten verloren 
gehen. Außerdem müsste ich mich mit viel mehr Fragen rumschlagen. Das 
überlass ich lieber etablierter Software.
Etwas ungenauere Werte kann ich dagegen gut verschmerzen. Äußert sich 
dann halt in ein paar Prozent mehr Rauschen, bei im Schnitt vielleicht 
40-50% Dateigröße.

Am Ende will ich die Daten per fuse-fs on-the-fly 
komprimieren/dekomprimieren um nen leichten Zugriff zu haben.
Evtl. auch nur Dekompression weil sich nach erster Komprimierung nur an 
den in der Datei gespeicherten Einstellungen noch was ändert.

Vlad Tepesch schrieb:
> Brauchst du denn diese hohe Auflösung?
> Du könntest die Signale eventuell verbessern, wenn du mehrere Pixel zu
> einem zusammenfasst.

Mag ich schon behalten.
Erstens weil ich se eigentlich brauch.
Zweitens kommen die RAW-Konverter dann evtl. nicht mehr mit (weil Kamera 
und Auflösung nicht mehr zusammenpassen).
Drittens ist der Gewinn dadurch nicht sooo groß wie auf Anhieb zu 
vermuten. Die Werte muss ich ja dann genauer speichern. Die 
Ortsauflösung wird aber geringer, so dass die Datei schon kleiner würde.

Vlad Tepesch schrieb:
>> Geht so nicht, weil der Rauschanteil mit dem Wert ansteigt (etwa
>> sqrt(BASENOISE^2+(a*value)^2)).
> Da sind meine Kenntniss zu begrenzt. Woher kommt das? und wo kommt der
> Basenoise her?

Basenoise ist hier das was man üblicherweise bei ner AD-Wandlung so hat. 
Sensor-/Verstärker-/Quantisierungsrauschen.

Ah Fehler. Muss sqrt(BASENOISE^2+a*value) sein.

Der wertabhängige Teil ergibt sich aus der Quantenphysik. Zahl der 
einfallenden Photonen, Konvertierung in Elektronen auf dem Sensor, etc. 
sind alles poisson-verteilte Zufallsprozesse. Die Varianz ist hier 
gleich dem Erwartungswert, bzw. Sigma ist sqrt(Erwartungswert).

Vlad Tepesch schrieb:
> Das beste wäre, du postest einfach mal ein Beispiel-File, um der
> Ursprünglichen Problematik wieder etwas näher zu kommen.

Stell ich heut abend zusammen und lads bei mir auf den Server. Minimum 
sind 2 Files, ich schätze aber es werden ein paar mehr.

Vlad Tepesch schrieb:
> Wobei mich das ganze grundsätzlich auch interessiert.
> Prinzipiell hört sich das ganze aber für mich danach an, als wenn der
> Sensor für den Anwendungsfall nicht geeignet wäre.

Das sag mal der Entwicklungsabteilung der Hersteller. Nennenswert mehr 
als ein Faktor 2 ist da denke ich grundsätzlich nicht drin.
Die Frage geht dann auch eher in eine andere Richtung. Sieht man von 
ISO3200 (ISO1600) und höher ab langt mir die Signalqualität ja. Ich kann 
sogar noch ein wenig Rauschen mehr (durch die Quantisierung) vertragen.

Ein um den Faktor 10 reduzierter Rauschanteil würde aber die 
Ausgangsdaten schonmal kleiner machen und die Entsorgung nicht 
benötigter Informationen definierter/leichter machen.

> Bei so lichtschwachen Szenarios wäre ein Monochromsensor wahrscheinlich
> sinnvoller, bei dem nicht schon mal eben 2/3 der einfallenden Energie in
> dem Filterpattern hängen bleibt.

Grundsätzlich schon richtig. Oft/Meistens will man halt auch Farbe.

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

Ich verstehe irgendwie nicht ganz wann die Kompression stattfinden 
soll? Auf der Kamera damit du mehr Bilder speichern kannst? Oder auf dem 
PC damit die Photos nicht soviel Platz wegnehmen. Allgemein bringen doch 
auch 7% "mehr" nicht so viel im Zeitalter der TB Festplatten, oder was 
ist der Hintergrund?

von Stephan (Gast)


Lesenswert?

Läubi .. schrieb:
> Ich verstehe irgendwie nicht ganz wann die Kompression stattfinden
> soll? Auf der Kamera damit du mehr Bilder speichern kannst? Oder auf dem
> PC damit die Photos nicht soviel Platz wegnehmen.

Kamera wäre toll, is aber nicht. Geht nur um den PC.

Läubi .. schrieb:
> Allgemein bringen doch
> auch 7% "mehr" nicht so viel im Zeitalter der TB Festplatten, oder was
> ist der Hintergrund?

Wegen 7% sicher nicht. Ich gehe von mindestens 50% aus, bei höheren ISOs 
mehr.

Für ISO3200 sind die Verhältnisse etwa so:
- Original CR2 (mit Vorschau): 30MB
- Original CR2 (ohne Vorschau): 24MB
- DNG (ohne Vorschau): 22MB
- die Rauschbits verworfen: 6-9MB
- bei nicht Top-scharfen Aufnahmen stärker komprimiert: 4-6MB

Ein JPEG bei höchster Qualität wäre größer, erlaubt kaum noch sinnvolle 
Korrekturen und hat auch wenn alle Einstellungen perfekt waren mehr 
Daten verloren als die stärkste verlustbehaftete Kompression die mir so 
vorschwebt.
JPEG weiß schließlich nichts davon, dass rund 2/3 der Daten "erfunden" 
(schlau interpoliert) sind und muss die halt mitkodieren.

Die Datenmenge an sich ist eigentlich nicht der Grund. Eher die 
Datenschieberei, Backups, Transfer übers Netzwerk/DSL.
Und wie bei allen Hobbyprojekten zum größten Teil halt die Interesse an 
der Sache.

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

Naja dann würde ich einfach bz2, rar, oder Zip nutzen da was eigenes zu 
stricken wird meistens nicht die gewünschten Ergebnisse bringen.
Das mit dem "Rauschbits" versteh ich zwar nicht, bin aber auch kein 
Digitalphoto Experte.
JPEG ist hier aber ungeeignet wenn du "höchste Qualität" wählst. Was bei 
mir irgendwie Verwirrung stiftet ist: Du willst einerseits verlustlos 
komprimieren, andererseits aber Sachen wegwerfen, das passt nicht so 
ganz zusammen.
Wenn du Daten "wegwerfen" kannst, dann tu das und komprimiere die Datei 
danach ganz einfach mit ZIP o.ä.

Wenn du unbedingt noch selbst was machen willst könnte auch LZW was 
bringen, benötigt aber ein 2-Pass beim de/komprimieren.

Huffman passt am besten auf Daten die aus einer "Zufallsquelle" mit 
bekannter Verteilung kommen. Mit Bildern hat man aber meist dies nicht 
gegeben.

von Stephan (Gast)


Lesenswert?

Beispieldaten gibts unter http://213.239.205.105/rawkompression/

Die meisten Daten sind im PGM-Format. Für schnelleren Download und als 
Referenz gibts zusätzlich jeweils eine bz2-komprimierte Variante.

Für mich interessant ist vor allem die Datei 
komprimiert_RGGB/green1_c.pgm.

Zur Erläuterung:

original:
Ausgangsdaten (CR2 und dng) sowie Graustufenbild (PGM) nicht nach Farben 
getrennt.

original_RGGB:
Die 4 Farbkanäle (rot, grün1, grün2, blau) als Graustufenbilder (PGM).

original_PNG_JP2K:
Herkömmliche (verlustlose) Kompression der Farbauszüge (JPEG2k, PNG, 
PNG+PNGCrush). Nur für Grün 1.

komprimiert_RGGB:
Verlustbehaftete Version als Graustufenbilder (im Abstand von 1 Sigma 
des Rauschens quantisiert). Praktisch also das Signal durch den 
Rauschpegel geteilt und gerundet.

dekomprimiert_RGGB:
Die "komprimierten" Graustufebilder wieder in den normalen Wertebereich 
verschoben. Praktisch mit dem Rauschpegel multipliziert (und wieder 
gerundet).
Diese Daten haben wieder den ursprünglichen Wertebereich und können mit 
den normalen Werkzeugen weiterverarbeitet werden. Die Entropie ist die 
gleiche wie in der komprimierten Variante.

Beispiele_JPEG:
Aus dem Original und der komprimierten(+dekromprimierten) Version 
erstelltes JPEG. Und die mit Faktor 128 verstärkte Differenz zwischen 
den beiden.

Hinweise

Die PGMs haben nen kleinen Header und dann kommen die Daten (hier 16bit) 
Zeilenweise. MSB-first.

Für die meisten werden die Daten recht unbrauchbar - im wesentlichen 
schwarz - aussehen. Das Ergebnis gibts unter Beispiele_JPEG. So grob von 
Hand "entwickelt". Normalerweise macht das die Kamera intern, bzw. wenn 
man mit RAW arbeitet ein RAW-Konverter.

In "komprimiert" ist nur die Entropie reduziert. Halt die Daten die noch 
zu komprimieren sind.

Grundsätzlich sollten sich die in "komprimiert" auch bester mit 
Algorithmen für Bildkompression zusammenarbeiten als die unter 
"dekomprimiert" (bzip scheints recht egal zu sein). "komprimiert" ist 
ziemlich glatt, "dekomprimiert" hat recht ungewöhnliche Sprünge.

Die Daten hier sind ISO100. ISO1600 probier ich nachher mal aus.

von Stephan (Gast)


Lesenswert?

Läubi .. schrieb:
> Naja dann würde ich einfach bz2, rar, oder Zip nutzen da was eigenes zu
> stricken wird meistens nicht die gewünschten Ergebnisse bringen.

Wenn dann bz2. Ist eine Variante die ich sicher nicht aus den Augen 
verliere.

Läubi .. schrieb:
> Was bei
> mir irgendwie Verwirrung stiftet ist: Du willst einerseits verlustlos
> komprimieren, andererseits aber Sachen wegwerfen, das passt nicht so
> ganz zusammen.

Ich mag Unsinn definiert wegwerfen, dann aber nicht noch undefinierte 
zusätzliche Verluste die von sonstwas abhängen.
Ne verlustbehaftete Kompression die sicher innerhalb der Grenzen bleibt 
die ich haben will wäre natürlich auch ok. Kenn ich leider keine 
entsprechende.


Der Thread driftet im Moment irgendwie ab. Das Thema insgesamt ist - 
auch für mich - recht komplex und ich kann die Detailfragen leider nicht 
schnell genug beantworten.

Ich hab erst mal einigen neuen Input. Danke an alle.
Vor allem meine Ausgangsfrage (macht es Sinn kleine Datenblöcke mit 
individuellen Tabellen auszustatten) ist eigentlich beantwortet.
Fürs erste werd ich die hier gewonnen Ideen mal antesten.

Ich schlag vor wir legen den Thread erst mal schlafen und ich komm 
darauf zurück wenn ich mehr weiß und die Sache besser beschreiben kann.
Falls jemand für die Beispieldaten ne schlaue Kompression finden sollte, 
natürlich immer her damit...

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

Stephan schrieb:
> Ich mag Unsinn definiert wegwerfen, dann aber nicht noch undefinierte
> zusätzliche Verluste die von sonstwas abhängen.
Okay. Dann solltest du dein Problem in zwei Schritte unterteilen:
1) "Unsinn"/Rauschen entfernen. Wenn es tatsächlich so ist das der 
Sensor nur 8 effektive Bits liefert, wurde ja oben schon genannt einfach 
die Daten entsprechend rechts schieben.
2) Komprimieren. Komprimieren kann nur Redundanzen entfernen, Rauschen 
ist aber keine Redundanz, das wirst du deshalb vorher machen müssen.

> Ne verlustbehaftete Kompression die sicher innerhalb der Grenzen bleibt
> die ich haben will wäre natürlich auch ok. Kenn ich leider keine
> entsprechende.
Naja, dabei müßtest du deine "Grenzen" erstmal definieren. Es gibt 
sicher kein Kompressionsverfahren welches "undefiniert" arbeitet ;)

von Stephan (Gast)


Lesenswert?

Läubi .. schrieb:
> Okay. Dann solltest du dein Problem in zwei Schritte unterteilen:
> 1) "Unsinn"/Rauschen entfernen. Wenn es tatsächlich so ist das der
> Sensor nur 8 effektive Bits liefert, wurde ja oben schon genannt einfach
> die Daten entsprechend rechts schieben.

Das ist gelöst. Sind keine pauschalen ##Bit, spielt aber für die 
Kompression keine Rolle.

> 2) Komprimieren. Komprimieren kann nur Redundanzen entfernen, Rauschen
> ist aber keine Redundanz, das wirst du deshalb vorher machen müssen.

Ist klar. Verlustlos komprimiert alle Daten die reinkommen 1:1.

Sowas wie JPEG (verlustbehaftet) wirft Daten weg. Was weggeworfen wird 
wurde irgendwann vmtl. anhand von Beispieldaten festgelegt. Funktioniert 
also nur für Daten die in etwa diesen Beispieldaten entsprechen.

Läubi .. schrieb:
> Naja, dabei müßtest du deine "Grenzen" erstmal definieren. Es gibt
> sicher kein Kompressionsverfahren welches "undefiniert" arbeitet ;)

Doch. Viele verlustbehaftete (auch verlustlose) betrachten 
Rundungsfehler (und die sind implementierungs-/plattformabhängig) als 
keine Verluste.
Eine differentielle Kodierung der Daten scheidet dann z.B. aus weil sich 
Fehler fortsetzen.
Bei JPEG (verlustbehaftet) sind z.B. harte Sprünge so ne Sache. Es ist 
leider relativ undefiniert was nachgeschaltete Software produziert wenn 
der Sprung (in z.B. nur einem Kanal) doppelt/halb so groß ist.

Auch wenn mich dein Post jetzt nicht direkt weiterbringt. Beim 
Beantworten fallen mir neue Sachen ein, bzw. Aspekte werden 
aufgefrischt.
Danke.

von Stephan (Gast)


Lesenswert?

Kurzer Zwischenstand

Ich hab viel gelernt, über bz2 nachgelesen und die Algorithmen getestet.

Die gute Kompression mit bz2 liegt im wesentlichen an "Move to Front". 
Die "Burrows-Wheeler-Transformation" bringt nur bei niedrigen ISOs was 
(Erklärung dafür hab ich keine, ein "Alphabet" existiert ja bei meinen 
Daten nicht).

"Move to Front" lässt sich bei meinen Testdaten zu 99% durch ne 
Differenzkodierung zu ca. 10% übertreffen.
Letztenendes ist "Move to Front" ja auch ein ähnliches Konzept, ist aber 
ein allgemeineres Konzept.
Ist aber noch ne Menge für mich zu testen.

von der mechatroniker (Gast)


Lesenswert?

> Eine differentielle Kodierung der Daten scheidet dann z.B. aus weil sich
> Fehler fortsetzen.

Die Aussage kann ich nicht so unkorrigiert stehen lassen. Das gilt 
nämlich nur in Bezug auf Übertragungsfehler, in Bezug auf 
Quantisierungs-/Rundungsfehler nur, wenn mans falsch macht.

Richtig: die Differenz zwischen dem Originalwert des aktuellen Samples 
dem aus dem kodierten Datenstrom zurückgewonnenen letzten Sample 
verwenden.
Falsch: die Differenz zwischen den Originalwerten verwenden.

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

Stephan schrieb:
> Sowas wie JPEG (verlustbehaftet) wirft Daten weg. Was weggeworfen wird
> wurde irgendwann vmtl. anhand von Beispieldaten festgelegt. Funktioniert
> also nur für Daten die in etwa diesen Beispieldaten entsprechen.
Nein, da wäre ja verherrend! Das ganze basiert natürlich (wie so oft) 
auf der Mathematik: http://de.wikipedia.org/wiki/JPEG

Stephan schrieb:
> Erklärung dafür hab ich keine, ein "Alphabet" existiert ja bei meinen
> Daten nicht
Das "Alphabet" sind einfach deine vorkommenden Datenblöcke.
z.Bl läßt sich das Wort "Hallo" durch das Alphabet [H, a, l, o] 
abbilden, das man bei mehr als 26 Zeichen langsam in Bereiche kommt wo 
man nichtmher jedes Zeichen sinnvoll mit einem Buchstaben belegen kann 
ist eine andere Sache ;)

Du darfst auch nicht immer nur versuchen deine paar Beispiele zu 
betrachten, dann passiert nämlich genau das:
> Was weggeworfen wird wurde irgendwann [...] anhand von Beispieldaten
> festgelegt. Funktioniert also nur für Daten die in etwa diesen
> Beispieldaten entsprechen.
Der Trick ist aber, das das ein Verfahren im Durchschnitt für eine große 
Menge an Eingangsdaten gute Ergebnisse liefert.

von Stephan (Gast)


Lesenswert?

der mechatroniker schrieb:
>> Eine differentielle Kodierung der Daten scheidet dann z.B. aus weil sich
>> Fehler fortsetzen.
>
> Die Aussage kann ich nicht so unkorrigiert stehen lassen. Das gilt
> nämlich nur in Bezug auf Übertragungsfehler, in Bezug auf
> Quantisierungs-/Rundungsfehler nur, wenn mans falsch macht.
>
> Richtig: die Differenz zwischen dem Originalwert des aktuellen Samples
> dem aus dem kodierten Datenstrom zurückgewonnenen letzten Sample
> verwenden.
> Falsch: die Differenz zwischen den Originalwerten verwenden.

Missverständnis. Die Differenzen der Originalwerte darf ich natürlich 
nicht nehmen.
Mir gehts darum, dass die Rekonstruktion nicht 100% festgelegt ist.

Bei JPEG ist meines Wissens nicht genau festgelegt mit welchen 
Genauigkeiten gerechnet werden muss, wann wie gerundet wird, etc. Da 
könnte dann je nach Implementierung/Plattform ein leicht anderes 
Ergebnis rauskommen.
Wenn ich so ein Verfahren für normalen Bilddaten verwende ists reichlich 
egal. +-1/256 an ein paar Stellen stört nicht. Für ne Differenzkodierung 
kommt es aber genau zu der Fehlerfortpflanzung.

Bei "verlustloser" Bildkompression werden Rundungsfehler gerne nicht 
beachtet. PNG eher nicht, JPEG-lossless + JP2K sicher, alle anderen 
Algorithmen mit Wavelets/farbraumtransformationen vermutlich auch.

von Stephan (Gast)


Lesenswert?

Läubi .. schrieb:
>> Sowas wie JPEG (verlustbehaftet) wirft Daten weg. Was weggeworfen wird
>> wurde irgendwann vmtl. anhand von Beispieldaten festgelegt. Funktioniert
>> also nur für Daten die in etwa diesen Beispieldaten entsprechen.
> Nein, da wäre ja verherrend! Das ganze basiert natürlich (wie so oft)
> auf der Mathematik: http://de.wikipedia.org/wiki/JPEG

Ist aber doch richtig. Farbraumumrechnung, optionale Unterabtastung 
4:x:x, Quantisierungsmatrix, ...
Alles vmtl. anhand von realen Daten (hier Fotos) festgelegt.

Am Ende steht natürlich ein definierter Algorithmus. Der taugt aber für 
andere Daten (z.B. ne Textdatei) nicht.

Läubi .. schrieb:
>> Erklärung dafür hab ich keine, ein "Alphabet" existiert ja bei meinen
>> Daten nicht
> Das "Alphabet" sind einfach deine vorkommenden Datenblöcke.

Hab schlecht ausgedrückt. Sagen wollte ich Wörter/Silben, hier typische 
Wertfolgen.
Mein Urteil zu "Burrows-Wheeler" war aber eh falsch.

von Stephan (Gast)


Lesenswert?

Läubi .. schrieb:
> Du darfst auch nicht immer nur versuchen deine paar Beispiele zu
> betrachten, dann passiert nämlich genau das:
>> Was weggeworfen wird wurde irgendwann [...] anhand von Beispieldaten
>> festgelegt. Funktioniert also nur für Daten die in etwa diesen
>> Beispieldaten entsprechen.
> Der Trick ist aber, das das ein Verfahren im Durchschnitt für eine große
> Menge an Eingangsdaten gute Ergebnisse liefert.

Grundsätzlich richtig. Im Moment dürften aber meine derzeit verwendeten 
3 Testbilder reichen.

Nutzdaten würde ich natürlich am liebsten gar keine verlieren, das lässt 
sich nur leider nicht trennen.
So wie derzeit eingestellt verliere ich 1-5% Nutzdaten. Rauschen macht 
dann noch um 50% der Daten aus, und die Werte sind vorgegeben.

Motivabhängig werden da letztenendes ein paar Prozentpunkte sein. Im 
Moment bin ich noch bei der Vorauswahl grundsäätzlich geeigneter 
Verfahren.
Solange da noch Schwankungen mit 1ß% auftauchen macht die Breite keinen 
Sinn.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.