ZITAT(Neonsquare @ 2013-01-09, 12:33) ZITAT(matthiaspaul @ 2013-01-08, 15:57) - cRAW ist kein verlustloses Kompressionsverfahren, wie verschiedentlich im Netz (auch hier im Forum, meiner Erinnerung nach auch von mir) geschrieben wurde. Tatsächlich ist es ein fünfstufig adaptives Verfahren, das hohe Präzision in Bereichen erlaubt, in denen diese "psychooptisch" gefordert ist, und dafür in anderen, weniger kritischen Bereichen ungenauer abbildet, um Bits zu sparen.[/quote]
Mir behagt die Bezeichnung "kein verlustloses Kompressionsverfahren" bzw. einfacher "Verlustbehaftetes Kompressionsverfahren" im Zusammenhang mit cRAW nicht. Nicht das es sicher falsch wäre - es ist nur einfach zuviel gefolgert, denn leider ist dcraw.c nur die eine Seite der Gleichung und wir können das Bild nicht in der von Dir genannten Art vervollständigen. Warum ist das so? Du vermutest als Begründung für die Adaption des Speicherformats "psychooptische" Effekte - also ähnlich wie bei JPEG oder wie mit MP3 bei Audio. Ich halte es aber für plausibler, dass die Grundlage der Adaption nicht der Mensch (psycho...) sondern die Kamera ist.
[/quote]
Da sprichst Du direkt mehrere sehr interessante Punkte an:
Zunächst mal, vermutlich hast Du Recht, daß der Algorithmus hier weniger oder gar nicht auf unsere Sehgewohnheiten Rücksicht nimmt, als mit Vorwissen um physikalisch-technische Gegebenheiten optischer oder elektronischer Natur die Genauigkeit der abgelegten Daten an die tatsächlich vor Ort von der Hardware erzielbare Genauigkeit anpaßt. Auf diese Weise kann dieser dafür optimierte Kompressionsalgorithmus mit relativ wenig Rechenaufwand und lokalem Speicherbedarf einen ziemlich hohen Kompressionsfaktor erreichen, was ja für die Implementierung im Signalprozessor der Kamera wichtig ist, damit die Daten mit nur minimalen Verzögerungen verarbeitet werden können.
Ohne, daß ich das jetzt genauer untersucht hätte, verlustlose Kompressionsalgorithmen nach Lempel-Ziv-Welch etc., ggfs. noch speziell für die vorliegende Aufgabe adaptiert, dürften zwar noch höhere Kompressionsraten schaffen, aber auch mehr Ressourcen verbrauchen und lassen sich vermutlich auch nicht so gut "streamen", aber das ist jetzt erstmal nur eine Vermutung.
Der zweite Punkt, den Du ansprichst, betrifft die Tatsache, daß wir ja nur die Dekompressionsroutine in dcraw kennen, nicht die Kompressionsroutine in der Kamera, und die Implementierung in dcraw basiert letztlich nur auf Reverse Engineering auf der Grundlage vorhandener ARW-Dateien, nicht auf irgendeiner offiziellen Dokumentation des Datenformats oder des Kompressionsverfahrens durch Sony. Würde es sich um ein verlustfrei arbeitendes Verfahren handeln, wäre das nicht wichtig. Nach einer gewissen Zeit des Experimentierens könnte man praktisch sicher sein, das richtige Dekompressionsverfahren gefunden zu haben und bräuchte sich keine Sorgen mehr zu machen. Gerade weil es sich aber nicht um ein verlustfreies Verfahren handelt, ist die fehlende offizielle Dokumentation hier, wie ich finde, problematisch, denn der Dekompressionsalgorithmus liefert zwar ein Ergebnis, das auf den ersten Blick auch sehr vernünftig aussieht, aber da das Ergebnis nicht bitidentisch mit dem sein muß, was zuvor in der Kamera vorlag, können wir nicht sicher wissen, daß dies wirklich alles ist, was hinter dem Verfahren steckt.
Ich habe ja weiter oben schon durchblicken lassen, daß der Dekompressionsalgorithmus bei mir verschiedene Fragen aufwirft, weil er an einigen Stellen sozusagen etwas "unrund" läuft, und ich vermute, daß Dir ganz ähnliche Dinge aufgefallen sind.
Es gibt z.B. eine ganze Reihe von Fällen, die überhaupt nicht berücksichtigt werden. Es ist möglich, daß diese Fälle in real existierenden ARW-Dateien einfach nie vorkommen und deshalb nicht berücksichtigt werden müssen, aber es wäre auch denkbar, daß der Kompressionsalgorithmus der Kamera hier durchaus noch etwas komplexer ist, als es uns der vorliegende Dekompressionsalgorithmus Glauben macht - und dann gingen bei der Dekompression u.U. "versteckte" Informationen verloren, die eigentlich noch genutzt werden könnten, um die Qualität der Dekompression zu verbessern.
Einige dieser Fälle ließen sich softwareseitig detektieren, da sie bestimmte "Muster" im 128-Bit-Datenblock erzeugen, die eigentlich nie vorkommen dürften. Andere Fälle könnten als Metadaten in den Nutzdaten selbst "versteckt" sein, und man würde sie ohne Vorwissen, daß sie existieren, nicht detektieren können (ähnlich wie Wasserzeichen) und dementsprechend auch nicht nutzen können.
Das sind Gründe, warum ich mir an dieser Stelle ein verlustfreies Kompressionsverfahren wünschen würde, so daß sich außerhalb der Kamera bitidentische Daten rekonstruieren lassen und man nicht darauf angewiesen bleibt, Daten bestmöglich zu "interpretieren".
Ich werfe mal ein paar Fragen auf:
- Man könnte vereinfachend annehmen, daß der Algorithmus so "binär" arbeitet, daß die Fensterposition, passend zur Fenstergröße, immer so entlang der Wertigkeit im Zweiersystem positioniert wird, daß das Fenster nie über den 11-Bit-Raum hinausragt. Nur in den Fällen, in denen das nicht so ist, können bei der min-Addition 12-Bit-Daten entstehen, die der Algorithmus dann sofort wieder auf 11 Bit zurechtstutzt:
1
2
if (pix[i] > 0x7FF)
pix[i] = 0x7FF;
Hier wäre zu klären, ob dieser Fall in der Praxis überhaupt vorkommt (da Du und Hans den Code in der Entwicklungsumgebung habt, könnt ihr ja mal im Debugger eine Trap auf diese Bedingung setzen). Falls nein, kann man sich die Abfrage sparen und bekommt einen Performance-Gewinn. Falls ja, stellt sich einerseits die Frage, ob es wirklich notwendig ist, die Daten zu clippen (etwa, weil sie dann auch invalide sind), denn eigentlich müßten wir froh über jedes zusätzliche Bit sein, und schließlich müßte dieser Fall auch durch curve[], dessen Eingangsindex ja 16 Bit breit ist, sauber abgefangen werden können (vorausgesetzt, die Kurve ist vollständig definiert). Außerdem ist anzunehmen, daß diese Daten, wenn sie denn tatsächlich im Nutzdatenstrom vorkommen, kein reines Artefakt sind, sondern auch Information enthalten. Warum sollten wir die durch Clippen verschenken? Die Beantwortung dieser Frage könnte auch Rückschlüsse auf die konkrete Implementierung in der Kamera in Bezug auf eine mögliche Rauschformung zulassen, die wir dekompressionsseitig zusätzlich ausnützen könnten, wenn wir darum wüßten.
- Warum ist der Algorithmus auf einen maximalen Shift-Wert (sh) von 4 beschränkt?
1
2
3
4
max = 0x7FF & (val = sget4(dp));
min = 0x7FF & val >> 11;
[...]
for (sh=0; ((sh < 4) && (0x80 << sh <= max-min)); sh++);
sh kann hier die Werte 0 bis 4 annehmen, die Fensterhöhen von 128, 256, 512, 1024 und 2048 Werten bzw. einer Multiplikation der 7-Bit-Werte mit 1, 2, 4, 8 oder 16 entsprechen. Da sh aber ausschließlich durch max und min bestimmt wird, bei denen es sich um 11-Bit-Werte (0..2047) handelt, stellt 2047-0 = 2047 den größten Wert auf der rechten Seite der Bedingung dar. Mit sh = 4 stünde auf der linken Seite 128 << 4 = 2048, also "2048 <= 2047", was zum Abbruch der Schleife führen würde. Demnach müßte der folgende kürzere (und möglicherweise sogar etwas schnellere) Code exakt das Gleiche bewirken und sich nebenbei "automatisch" an noch größere Fensterhöhen anpassen, sollte(n) min (und max) auf mehr als 11 Bit erweitert werden:
1
for (sh=0; 0x80 << sh <= max-min; sh++);
Da stellt sich dann direkt die Frage, ob es einen Grund geben könnte, den Algorithmus an dieser Stelle künstlich auf 11 Bit zu begrenzen, wenngleich er eigentlich auch mit mehr Bits arbeiten würde.
- Die nächste Überlegung zielt darauf ab, ob der Algorithmus korrekt reagiert, wenn die von max und min aufgespannte Fensterhöhe kleiner als 128 Werte (entsprechend der bereitgestellten 7-Bit-Daten) werden würde. Meiner Analyse nach würde der Algorithmus mit dieser Bedingung robust weiterarbeiten, d.h. er würde weiterhin eine Fensterhöhe von 128 Werten annehmen (warum sollte man weniger nehmen, wenn schon mal 7-Bit-Daten geliefert werden? - außer die LSBs des 7-Bit-Wertes müßten dann anders interpretiert werden), d.h. es würde zunächst einmal überhaupt nicht auffallen, wenn diese Bedingung in real existierenden Rohdaten tatsächlich vorliegt - der Dekompressionsalgorithmus würde vernünftige Daten liefern.
Hat das schon mal jemand untersucht, ob es Dateien, z.B. angebliche 14-Bit-Dateien von der SLT-A99 gibt, in denen diese Bedingung vielleicht erfüllt ist?
Ich frage dies, weil dies eine Möglichkeit für Sony wäre, zusätzliche Bits für max und min unterzubringen, die ein Algorithmus, der davon weiß, nutzen kann, die aber ein Algorithmus wie der obige einfach überlesen würde. Wie das?
Beispiel:
Die Differenz max-min wird bisher implizit als mindestens 128 angenommen (eigentlich: größer 64), nennen wir dies mal Fall 1. Wäre sie nun kleiner-gleich 64, könnte man diese Bedingung als Fall 2 annehmen, kleiner-gleich 32 wäre Fall 3, kleiner-gleich 16 Fall 4, kleiner-gleich 8 Fall 5, kleiner-gleich 4 Fall 6, kleiner-gleich 2 Fall 7, kleiner-gleich 1 Fall 8, gleich 0 Fall 9. In 8 Fällen kann man 3 unabhängige Bits kodieren.
Ein weiteres Bit könnte man in der Bedingung unterbringen, ob die Differenz aus max-min positiv oder negativ ist. Würden die beiden Werte im Header vertauscht, würde der bisherige Algorithmus nicht mehr arbeiten, ließe sich aber leicht anpassen, indem er die Werte für die weitere Auswertung einfach zurücktauscht, sich aber merkt, daß sie vertauscht waren und dies als viertes unabhängiges Bit betrachten.
Auf diese Weise könnten wir also ohne Änderung des Verfahrens je ein zusätzliches LSB für min und max herbeizaubern (also 12 Bit statt 11 Bit), die ein herkömmlicher Algorithmus einfach überlesen würde. (Dies allerdings nur für Fensterhöhen von maximal 64.)
Mit einer minimalen Änderung des Verfahrens (max-min Differenz positiv/negativ) wären sogar zwei Bits für min und max zu holen (also 13 Bit statt 11 Bit).
Und nach einer weiteren kleinen Änderung könnte man für Fensterhöhen von maximal 64 Werten die niederwertigsten Bits des 7-Bit-Wertes nicht, wie gehabt, als Teil des Faktors interpretieren, sondern könnte jedem der 14 Werte ein zusätzliches unabhängiges LSB spendieren, so daß diese nicht vom LSB von min abhängen. Diese Änderung, nach dem alten nicht angepaßten Algorithmus interpretiert, würde allerdings gewisse Artefakte erzeugen, die vermutlich als etwas stärkeres Rauschen sichtbar würden.
Provokante Frage: Würden wir es merken, wenn Sony etwas in dieser Art schon implementiert hätte und dcraw die Daten zwar immer noch plausibel, aber nicht mehr "korrekt" interpretiert, so daß die darauf basierenden Konverter z.B. aus SLT-A99-Dateien nicht alles rausholen, was drin ist?
- Was ist mit dem pathologischen Fall max = min? In diesem Fall wird ein Fenster der Höhe 0 aufgespannt. Der Algorithmus in der bisherigen Form ließe sich davon nicht beeindrucken und würde die restlichen 14 Rohdaten immer noch aus den 7-Bit-Daten generieren, obwohl doch eigentlich (zumindest kann man eine solche Implementierung in der Kamera wohl annehmen) bereits feststeht, welchen Wert sie haben.
Normalerweise müßten dann ja die 7-Bit-Werte auch alle 0 sein, aber was ist, wenn dies in real vorliegenden Daten nicht der Fall sein sollte? Hat schon mal jemand auf diese Bedingung im Debugger geprüft? Es wäre immerhin denkbar, daß die restlichen 14 mal 7 Bit-Daten dann anders zu interpretieren wären.
Sollte max = min gar häufiger vorkommen, könnte man dies auch als Sonderfall behandeln, um den Algorithmus zu beschleunigen (allerdings nur dann, wenn alle 7-Bit-Werte dann auch immer auf 0 bleiben).
ZITATAllerdings war cRAW auf jeden Fall bislang kein Hindernis - niemand hat je zeigen können, dass damit überhaupt irgendein Unterschied rauskommt. Es hängt eben doch von der Verteilung des Eingabekanals ab ob sich cRAW überhaupt "Verlustbehaftet" ausdrücken kann.[/quote]
Hier wird ein "echtes" 12-Bit-RAW mit dem cRAW-komprimierten Bild überlagert und die Unterschiede sichtbar gemacht:
http://www.dyxum.com/dforum/the-consolidat...230.html#316230
http://www.dyxum.com/dforum/the-consolidat...433.html#316433
Da dies natürlich nur auf der Basis des dcraw-Dekompressionsalgorithmus passiert, der, wie oben angedeutet, möglicherweise noch etwas an Qualität verschenkt (weil wir die genaue Implementierung des Kompressionsalgorithmus in der Kamera nicht kennen), ist das Ergebnis real eventuell etwas weniger ausgeprägt, aber das Bild zeigt in jedem Fall anschaulich, wo der cRAW-Algorithmus seine Schwächen hat (wobei das Motiv noch sehr gutmütig ist).
Angenommen, genau diese Bereiche würden nun in einer weiteren Verfeinerung des Verfahrens verlustfrei (ob unkomprimiert oder nach einem anderen Verfahren komprimiert) gespeichert, würde Sony mit geringem Mehraufwand auch eine tatsächlich verlustfreie Kompression realisieren können, die über jeden Zweifel erhaben ist.
Um nur mal ein Beispiel zu bringen, wie einfach man sowas implementieren könnte:
Enthalten max und min im Header den gleichen Wert, wird effektiv kein Fenster aufgespannt, der Algorithmus in der bisherigen Form also ad absurdum geführt (s.o.). Dieser Fall könnte dahingehend ausgelegt werden, daß die Daten in diesem 128-Bit-Block anders interpretiert werden müssen als sonst. Allerdings gingen dafür schon mal 2*11 Bits drauf, insgesamt würden aber 8 14-Bit-Werte (Verlust: 16 Bits, davon frei nutzbar: 5 Bits), 9 12-Bit-Werte (Verlust: 20 Bits, davon frei nutzbar: 9 Bits, es wären also auch 9 13-Bit-Werte realisierbar) oder 10 11-Bit-Werte (Verlust: 18 Bits, davon frei nutzbar: 7 Bits) in den Datenblock passen.
Alternativ und noch weniger verschwenderisch vielleicht die ebenfalls bisher nicht genutzte Bedingung, daß imax = imin ist (eine Bedingung, die in bisherigen Nutzdaten definitiv nicht vorkommen "darf", denn sonst würde der dcraw-Dekompressionsalgorithmus dahingehend versagen, daß er nämlich einen der 16 Werte des Blocks nicht initialisieren würde - dessen 7 Bits blieben dann ungenutzt und könnten im Prinzip eine andere Bedeutung haben), womit wir nur 2*4 Bit verschwenden, von denen wir 4 sogar wieder "recoveren" können, da es ja 16 Bitkombinationen gibt, die alle das Gleiche aussagen.
Dann würden ebenfalls nur 8 14-Bit-Werte (Verlust: 12 Bits, frei nutzbar, es wären also auch 8 15-Bit-Werte realisierbar), aber schon 10 12-Bit-Werte (Verlust: 4 Bits, frei nutzbar) oder 11 11-Bit-Werte (Verlust: 3 Bits, frei nutzbar) in den Datenblock passen.
Das könnte mit minimalem Aufwand ohne zusätzliche Ressourcennutzung in den bestehenden Kompressions- und Dekompressionscode integriert werden. Kameraseitig entstünde lediglich in einem Punkt Zusatzaufwand, nämlich zu erkennen, wann statt das bisherige Kompressionsverfahren anzuwenden die Daten nun einfach gespeichert werden sollten.
Der Kompressionsalgorithmus in der Kamera müßte also dahingehend verfeinert werden, daß er überwacht, ob Präzision verloren geht. Die Kamera würde dann einfach die laufende Kompression des aktuellen Datenblocks abbrechen und die vorliegenden Daten gemäß obiger Verteilung unkomprimiert wegspeichern.
Vielleicht übersehe ich hier irgendwas in dieser ad-hoc-Betrachtung, aber alle gängigen Prozessoren bieten z.B. diverse Flags an (z.B. Underflow, Overflow, Carry), die man geschickt abfragen kann, um zu erkennen, daß bei einer Operation z.B. ein Divisionsrest entstanden ist, was, wenn er im weiteren Verlauf unter den Tisch fällt, einen Genauigkeitsverlust bedeutet, den die Dekompression auf der anderen Seite nicht wieder zurückholen kann.
Da solche Informationen quasi als Abfallprodukt anfallen und entweder genutzt werden können oder eben nicht, sollte sich der zusätzliche Rechenaufwand dafür in engen Grenzen halten und keinesfalls den doppelten Aufwand ausmachen.
Auch ist das eine Operation, die sich sehr gut für eine Parallelisierung und Implementierung in Hardware-Logik eignen würde, bei der dann einfach der gleiche Datensatz nach verschiedenen Verfahren bearbeitet wird und nachher nur das beste Ergebnis übernommen wird.
Ich fände eine solche Verfeinerung des Verfahrens ziemlich erstrebenswert.
Viele Grüße,
Matthias