Laden...

Raster-/Pixel basiertes Datenformat

Erstellt von Merti_berg vor 9 Jahren Letzter Beitrag vor 9 Jahren 3.464 Views
M
Merti_berg Themenstarter:in
91 Beiträge seit 2008
vor 9 Jahren
Raster-/Pixel basiertes Datenformat

Hallo zusammen,
ich sitze schon seit einer Weile an einem Projekt und mache mir Gedanken zur effektivsten Speicherung von Daten.

Kurz zum Ziel:
-Daten sollen in einem Raster, also X und Y basierend, gespeichert werden (Datei)
-Bei den Daten handelt es sich um Zahlen in verschiedenen vorher festgelegten Wertebereichen, zB. 0-10, 0-10000000, usw...
-Die Anzahl der Daten kann sich unterscheiden.

Kurz zum aktuellen Stand:
-Im Moment nutze ich das .png Format, also ein Bildformat um die X und Y Daten zu speichern.
-In den Kanälen (bei einem 32bit Bild) speichere ich die Werte
-Die Zahlen werden durch Bitshifting so umgebaut, das der Wertebereich optimal ausgenutzt wird und danach gleich der nächste Bereich angehangen wird
-Also vereinfacht gesagt, die ersten 5bit für Wert1, die nächsten 4bit für Wert2, die nächsten 10bit für Wert3, usw...
Wie gesagt, das wäre jetzt am Beispiel eines 32bit Bildes mit 4 Kanälen (4 byte Arrays/32bit).

Ich möchte es so das wirklich jedes byte optimal genutzt wird. Also für die Zahl "20" brauche ich keine 32bit (int32), sondern nur 5. So das der Rest anschließend angesetzt wird. Speichereffizienz/Dateigröße ist hier sehr wichtig.

Ich hoffe das ist etwas verständlich.
Allerdings ist hier das Problem, wenn ein einzelner Wert schon größer als 32bit ist, oder mehrere einzelne Werte größer als 32bit sind, 2 oder mehr Bilder benutzt werden müsen.
Zudem läuft das Bitshifting immer nur mit Int32.

Meine Frage an euch, habt ihr Ideen ob es Dateiformate gibt welche meinen Anforderungen entsprechen oder Anregungen wie ich sowas besser und/oder effektiver umsetzen kann?

Eine andere Überlegung von mir wäre gewesen, die Daten mit X und Y (jeweils kleinstmöglicher Datentyp), stupide in eine Binärdatei zu packen und diese zu komprimieren.

16.807 Beiträge seit 2008
vor 9 Jahren

Wenn Du in jeder Zeile einer Spalte den gleichen Typ hast (Char, Int16), dann funktioniert das. So funktionieren auch relationale Datenbanken.
Ist in Spalte 3 mal ein Int32, mal ein Int16, dann funktioniert Dein Vorhaben ohne Metadaten wieder nicht. Dann musst Du Dir einen Header basteln, der auch wieder Platz kostet. Gewonnen hast dadurch nichts - wahrscheinlich sogar im Gegenteil.

Je nachdem in welchem Umfeld Du Dich bewegst ist Speicher auch günstiger als Rechenleistung.
Deswegen macht man sich bei den meisten Projekten auch eher um die effizienteste Verarbeitung statt Speicherung Gedanken.
Auch komprimieren kostet Rechenleistung. Besonders kompakt/effizient (=>schnell), flexibel und deswegen im Web sehr beliebt ist Json. Auch der Overhead ist sehr gering.
Das dazugehörige Binärformat, das einige NoSQL Datenbanken wie MongoDB nutzen, nennt sich Bson. Hat aber nur 4 numerische Datentypen (byte, int32, int64, double).

49.485 Beiträge seit 2005
vor 9 Jahren

Hallo Merti_berg,

mir scheint, dass du hier das PNG-Format eher miss- als gebrauchst. Jedenfalls scheint mir, dass man auf dem Bild nichts sinnvolles erkennen kann, wenn die Werte über die Bit-Grenzen der Farbkanäle hinweg kodiert werden.

Ich sehe keinen Grund, warum du nicht dein eigenes Datenformat verwenden solltest.

Ein bisschen klingt mir deinen Anforderungen nach Huffman-Kodierung oder allgemeiner Entropiekodierung.

Möglicherweise wäre auch die nachträgliche Kompression (im Sinne von Zip o.ä.) eine Option.

herbivore

742 Beiträge seit 2005
vor 9 Jahren

Du hast noch gar nicht erklärt, wieso das so effektiv sein soll. Falls 32 bit für dich ausreichen und du eine gute Bibliothek für PNGs hast, würde ich dabei bleiben. Das ist ein sehr kompaktes Format mit Kompression und Filter, die auch noch einiges an Platz sparen. Ob du jetzt was aus dem Bild erkennen kannst, ist meiner Meinung nach egal, in der Grafikprogrammierung werden Texturen ja auch zu mehr verwendet. Das arbeiten auf Byte-Ebene empfinde ich in C# manchesmal als sehr nervig und man muss extrem aufpassen, was man tut. Das Potential in Bezug auf Lesegeschwindigkeit was "kaputt" zu machen ist sehr groß.

1.361 Beiträge seit 2007
vor 9 Jahren

Hi Merti_berg,

zunächst musst du dir überlegen, was dein primäres Ziel sein soll.*Geschwindigkeit beim kompletten Einlesen *Geschwindigkeit / Overhead beim selektiven Einlesen einzelner Elemente *Geschwindigkeit beim Schreiben *Möglichkeit Teile zu aktualisieren *Festplattenverbrauch

Manche Dinge gehen einher, manche sind eher komplementär.
Beispielsweise kann eine Kompression für geringeren Festplattenbedarf gleichhzeitig die Geschwindigkeit für das komplette Einlesen optimieren. Schließlich ist fast immer (sofern du die CPU während dem IO-Warten nicht auslastest) das Einlesen einer komprimierten Datei und On-The-Fly-Dekompression schneller. (vergl. Blosc) Wenn du aber schnell auf einzelne Werte zugreifen musst, ist es hingegen schlecht, wenn die komplette Datei noch einmal komprimiert wurde.

Die Idee PNG zu missbrauchen ist ja eigentlich ganz clever.
Wobei PNG nicht viel Magie ist.
Raster-weises abspeichern, differentielle Kodierung gegenüber dem Wert links/oben vom aktuellen und abschließend eine Deflate-Komprimierung. Mach das einfach genau so selbst.

Fragen musst du dich aber auch, welche Reihenfolge die Daten haben sollen:*Zeilenweise und dann innerhalb eines Pixels die verschiedenen "Kanäle" *Spaltenweise und dann innerhalb eines Pixels die verschiedenen "Kanäle" *Kanalweise und innerhalb eines Kanals hintereinander zeilen-/spaltenweise alle zugehörigen Werte" *...

Das hängt davon ab, wie du später auf die Daten zugreifen möchtest. Zudem beeinflusst das Layout auch, wie gut eine Kompression arbeiten kann.
Wahrscheinlich lassen sich (sofern deine Differenzkodierung) die Kanäle einzeln besser komprimieren. Das spart auch zu ekliges Bitshiften. Der Zugriff auf alle Daten zu einem (X,Y)-Paar ist dann hingegen aufwändig und du musst alles dekodieren. Wenn die Dateien aber nur klein sind, kein Problem.
Also ein gedankliches Für- und Wieder 😃

Und ja, wenn du anschließend eine gute Kompression nutzt, sollte es nur einen geringen Unterschied machen, ob du führende Nullen mit kodierst - also 32-Bit Zahlen abspeicherst, obwohl deine Zahlen nie größer als 20 Bit sind.
Aber probier es am besten einfach aus.

beste Grüße
zommi

49.485 Beiträge seit 2005
vor 9 Jahren

Hallo zommi,

gerade weil die Speicherung der Werte nach den Vorstellungen von Merti_berg nicht an Byte-Grenzen aligned werden soll, wird die Differenzcodierung wohl nicht besonders wirksam sein, da dadurch auch wenig signifikante Bits großen Einfluss auf Byte-Werte haben. Das war mit ein Grund, warum ich mich gegen PNG ausgesprochen habe. Das "nichts zu erkennen" hob auch eher auf den negativen Effekt des nicht-aligned Speichern ab.

herbivore

1.361 Beiträge seit 2007
vor 9 Jahren

Hey,

ja klar, die Differenzkodierung muss schon "sinnvolle" Differenzen bilden. Und PNG macht das eben nur auf 8 oder 16 Bit Basis. Wenn ich diese aber nur mit bit-verschobenem Brei fülle, verschleiert er natürlich jedwede Redundanz vor dem Kompressor.

Man muss einem Kompressions-Algorithmus schon zuarbeiten, und es ihm leicht machen, die Redundanzen zu entdecken. Daher kann es auch effektiver sein, ein paar 0-Bits einzustreuen, damit ein byte-weise arbeitender Kompressor die Muster besser erkennt und ausnutzen kann.

Und ich meinte mit "clever", dass die Konzepte bei PNG 1:1 auch bei Merti_berg gut passen. (rasterbasiert, differenzkodiert, deflate).

Aber ich stimme dir völlig zu. Sich in die Beschränkungen von PNG reinzupressen macht keinern Sinn. Schließlich handelt es sich nicht um Farbbilder. Und da die Ideen hinter PNG leicht selbst zu implementieren sind, ist ein eigenes Dateiformat die beste Wahl.

beste Grüße
zommi

S
64 Beiträge seit 2008
vor 9 Jahren

Hallo Merti_berg,

wenn es um größere Datenmengen geht, kann sich auch mal ein Blick auf das HDF5-Format lohnen http://www.hdfgroup.org/. Da kann man so ziemlich alles Speichern, auch Kompression wird unterstützt.

Grüße
Maik

M
Merti_berg Themenstarter:in
91 Beiträge seit 2008
vor 9 Jahren

Hallo,

danke erstmal für eure zahlreichen Antworten. Ich probiere erstmal auf alle Fragen/Anmerkungen einzugehen.

Wie ihr schon gemerkt hab "missbrauche" ich das .png Format, da im Resultat darauf nichts sinnvolles zu erkennen ist, sondern nur die Werte gespeichert werden.

Die Dateigröße ist wichtiger als die Performance, da die Daten im nächsten Schritt zwischen Clients und Server ausgetauscht werden müssen, deshalb soll die Speicherung der Daten so effizient wie möglich umgesetzt werden.

32bit werden nicht ausreichen, da wir unterschiedliche Quellendaten haben. Dh. bei einer Quelle würden 32bit reichen, bei der anderen widerrum nicht.
PNG-Bibliothek verwende ich im Moment keine, nur die eingebauten Funktionen des .NET-Frameworks.

Es ist vorerst nicht angedacht, einzelne Teile der fertigen Datei auszulesen, sondern nur im Ganzen.

Ich hoffe ich bin soweit auf alles eingegangen, falls ich was übersehen haben sollte, gebt Bescheid.

Was ihr geschrieben habt, die Werte komplett in ein byte(Array) zu packen, ohne die byte-Grenzen zu überschreiben, ist mir auch durch den Kopf gegangen. Hier müsste ich mal eine Teststellung zusammenbauen und mir die Ergebnisse angucken.

/edit: hdf5 guck ich mir mal an.

849 Beiträge seit 2006
vor 9 Jahren

Hallo,

vorrausgesetzt Du benutzt auf beiden Seiten .net würde ich dir den UniversalSerializer vorschlagen. Bisher hab ich meine Dateien noch mit nichts kleiner bekommen. Und schnell ist er auch.

Allerdings habe ich auch noch nie den Drang verspürt ein eigenes Dateiformat wegen der Größe einer Datei zu etablieren.

16.807 Beiträge seit 2008
vor 9 Jahren

Die Dateigröße ist wichtiger als die Performance, da die Daten im nächsten Schritt zwischen Clients und Server ausgetauscht werden müssen, deshalb soll die Speicherung der Daten so effizient wie möglich umgesetzt werden.

Was ist ein Client? BDE? Handy? PC im Unternehmen?

Denn auch hier gilt: was ist entscheidend?

Dir bringt es nichts 10 Sekunden in der Übertragung zu sparen, wenn Du beim Lesen der Datei 30 Sekunden mehr brauchst, weil die (Thin-)Clients nicht die erforderliche Performance haben und zusätzlich beim Schreiben einen zeitlichen Aufwand hast.
Sagt Dir das Stichwort "sizing" was?

Gerade bei heutigen Bandbreiten in Unternehmen und Städten würde ich der Größe eine untergeordnete Rolle einräumen.

4.221 Beiträge seit 2005
vor 9 Jahren

@Abt: sehe ich auch so. Wir übertragen Daten an MDE (Win-CE/win-Mob) und zippen diese auch erst ab einer gewissen Grösse... (da es erst ab einer gewissen Grösse wirklich Vorteile bringt... vorher bringt es eher Nachteile)

Gruss
Programmierhans

Früher war ich unentschlossen, heute bin ich mir da nicht mehr so sicher...

5.657 Beiträge seit 2006
vor 9 Jahren

Hi Merti_berg,

Die Dateigröße ist wichtiger als die Performance, da die Daten im nächsten Schritt zwischen Clients und Server ausgetauscht werden müssen, deshalb soll die Speicherung der Daten so effizient wie möglich umgesetzt werden.

Es gab mal ein schönes Video von einer Google-Konferenz, wo erklärt wurde, wie die Entwickler (3D- und andere) Daten für den Google Body Browser aufbereiten und an den Browser schicken.

Ich finde das Video gerade nicht, aber nach meiner Erinnerung funktionierte das so:

  • Die Daten werden im ersten Schritt quantifiziert, denn bei 3D-Daten ist die Genauigkeit nicht so wichtig. Ein Float-Wert zwischen 0.0 und 1.0 wird dann z.B. in einen 16-Bit-Integerwert umgewandelt.

  • Dann werden die Integerwerte so kodiert, daß die Werte immer die Differenz zum vorherigen Wert darstellen ("Delta Coding"). Aus [100, 110, 109] wird dann [100, 10, -1]. Da es sich bei diesen speziellen Daten hier meistens um sehr kleine Werte handelt, können die in einem späteren Schritt besser komprimiert werden, als die Originaldaten.

  • Um diesen Effekt noch zu verstärken, kann man bspw. die Ausgangsdaten geschickt sortieren.

  • Das Ganze wird im JSON-Format als ganz normaler Text ausgegeben und vom Server mit GZip komprimiert an den Client geschickt. Dort werden die Daten wieder per JavaScript eingelesen und entpackt.

Eine Alternative wurde in dem Video auch vorgestellt. Dabei wird statt den JSON-Daten ein UTF8-Text erstellt und an den Client geschickt. Hier wird das Feature von UTF8 ausgenutzt, daß man für einen 7-Bit-Wert nur ein Byte verschicken muß, und größere Werte dann entsprechend mehr Bytes benötigen. Hat man hauptsächlich kleine Werte (siehe Schritt 2), dann ergibt sich eine entsprechende Komprimierung. Das Ganze kann dann auch wieder per GZip komprimiert ausgeliefert werden.

Wunder darfst du dir davon nicht erwarten, aber soweit ich es in Erinnerung hat, konnten die Body-Daten auf etwa ein Drittel reduziert werden. Sicher bin ich mir da aber nicht mehr.

Christian

Edit:
Ich habe noch ein paar Folien dazu gefunden, sowie eine Implementierung.

Weeks of programming can save you hours of planning