Pfiffiges Speicherformat für Punktlisten gesucht

[Medium]

Aloah!

Ich kämpfe gerade damit Punktlisten möglichst platzsparend auf Platte zu bringen. Dabei zählt wirklich jedes Bit, da es letztlich um eine Kompression geht. Die Punktlisten beinhalten folgendes:
- Punkte (uh baby)
Jeder Punkt besteht dabei aus:
- Seine X und Y Koordinaten; Größenordnung 0..1000 im Regelfall (geht um Bilder, später evtl. Video-Frames bis hin zu Full HD)
- Einen 2D-Vektor (X, Y); Größenordnung -64..63; Das ist ein skalierter Normalenvektor eines Ursprungspfades
- Zwei Farben

Aus diesen Infos werden später 2 Pfade erzeugt, die quasi-parallel verlaufen (Punkt +/- Normalenvektor), wobei jeweils einer eine der 2 Farben pro Punkt abbekommt. Diese zwei Farben sind dabei meist sehr unterschiedlich, also hilft eine paarweise Differenzbildung hier denke ich kaum.

Folgendes habe ich schon getan:
Nur der erste Punkt wird mit vollen 32bit Koordinaten gepeichert, von da an nur noch die Differenzen zum vorigen Punkt. Da sicher gestellt ist, dass dieser in einem Radius von 63 Pixeln liegt, passen die Differenzkoordinaten in Signed-Bytes. Gleiches gilt für die Normalen. Diese ließen sich theoretisch auch auf -32..31 reduzieren, jedoch ist das Bit gewinn auf 2 Koordinaten schwer gewinnbringend einzusetzen, da ich dann 2-Bit-Verschiebungen bekäme die ausgesprochen "nasty" wären.
Den Farbwert hab ich mal als 24bit RGB genommen, aber auch mal ein YCC Format probiert, bei dem ich die beiden Farbkomponenten in ein Byte gequetscht hab. Da dies aber nur je 16 Abstufungen zulässt, war das Ergebnis nicht gerade brauchbar. 32 Abstufungen dagegen wären schon besser, aber ähnliches Problem wie vorher: 1 Bit mehr = ekelhafte Verschiebungen im kompletten Stream.

Folgliiich kam ich auf ca. diese Größenordnungen:
Fall 24bit RGB:
Erster Punkt 4+4+1+1+3+3=16 Bytes, jeder weitere Punkt 1+1+1+1+3+3=10 Byte. Bei einem 10-Punkte Pfad also z.B. 106 Byte.
Fall 16bit YCC:
Erster Punkt 4+4+1+1+2+2=14 Bytes, jeder weitere Punkt 1+1+1+1+2+2=8 Byte. Bei einem 10-Punkte Pfad also z.B. 86 Byte. Aber eben indiskutable Farbreduktion.
Jedem Pfad ist zudem ein 32bit Integer vorangestellt der die Länge der folgenden Daten in Bytes angibt um mehrere solcher Listen voneinander trennen zu können. Mehrere Pfade haben keinerlei ausnutzbare Abhängigkeit voneinander.

Ich komme im Schnitt auf ca. 1000 Pfade á 10 Punkte, was im ersten Fall rund 107kB ergibt. Das ist mir zu viel! Zielgrößenordnung sollte irgendwo ab 50k bis 75k für eine solche Menge liegen, sehr gerne auch weniger.

Ich kann wie gesagt durchaus auf eine Qualitätsreduktion bei den Farben eingehen, nicht aber so wie in meinem Versuch. Auch ist 100%ige Pixelgenauigkeit nicht erforderlich. So ein Punkt kann gern auch mal 1-2 Pixel daneben liegen, es sollte im Großen und Ganzen aber nicht zu arg werden.

Hat hier noch jemand einen supergenialen Einfall wie ich das noch weiter zusammenstauchen könnte, oder bin ich auf verlorenem Posten?

Heissen Dank im Voraus!

[himitsu]

Zitat:

Jeder Punkt besteht dabei aus:
- Seine X und Y Koordinaten; Größenordnung 0..1000 im Regelfall (geht um Bilder, später evtl. Video-Frames bis hin zu Full HD)
- Einen 2D-Vektor (X, Y); Größenordnung -64..63; Das ist ein skalierter Normalenvektor eines Ursprungspfades
- Zwei Farben

+

Zitat:

Ich kann wie gesagt durchaus auf eine Qualitätsreduktion bei den Farben eingehen,

kx(1001)+ky(1001)+vx(128)+vy(128)+2*farben(24 bit)

in Bit
kx(10)+ky(10)+vx(7)+vy(7)+2*farben(24)

für 'ne kleine Ungenauigkeit könnte man ja einfach je das niedrigste Bit weglassen und so die Genauigkeit um den Faktor 2 herabsetzen
kx(9)+ky(9)+vx(6)+vy(6)+2*farben(21) = 72 Bit = 9 Byte pro Punkt


oder hab ich da jetzt etwas übersehn?

[Medium]

Bei den Farben wäre das sogar vertretbar, bei den Normalen schon recht schmerzhaft (da diese eh in den meisten Fällen nur -8..8 sind, aber die seltenen größeren recht wichtig sind), bei den Koordinaten schon unbrauchbar. Letzteres vorwiegend weil sich der Fehler beim 10. Punkt schon ziemlich übel aufaddiert hat, im schlimmsten Fall eben 10 Pixel vom Zielort weit weg. Das geht leider garnicht.
Schön wäre es wenn ich das so machen könnte, da man wieder genau an Bytegrenzen für einen Punkt käme. Allerdings ist die Reduktion um den Faktor 1/10 leider recht gering für die Fehler die dabei entstehen würden :?

Wobei... man könnte bei den Koordinaten noch bei der Differenzbildung dem Aufaddieren von Fehlern entgegenwirken wenn man's nicht ganz dumm anstellt. Aber die Normalen sind mir hier ein großer Dorn im Auge, und ohne diese der gleichen Behandlung zu unterziehen lande ich wieder an "krummen" Bitlängen (also nicht durch 8 teilbar). Hmmmhmhmhmmm :gruebel:

[OldGrumpy]

Du wirst viel mehr rausholen können wenn Du nicht das letzte Bit aus dem Datenformat rausquetscht sondern die fertige Punkteliste danach durch einen handelsüblichen Kompressor jagst. Damit kannst Du dann nämlich viel mehr Redundanzen auflösen als mit der künstlichen Vergröberung der Präzision. 16 Byte pro Datensatz ist doch gar nicht schlecht, allerdings frage ich mich wozu Du 32 Bit für X/Y brauchst wenn die Koordinaten maximal bis FullHD gehen. Da kommst Du doch locker mit 16 Bit pro Wert aus, die Du dann natürlich in einem DWord kombinieren kannst. Zudem finde ich es vorteilhaft, wenn man ein Format relativ mühelos lesen kann und nicht mit jedem Bit herumjonglieren muss. :)

[Medium]

Ich hab durchaus testweise mit 7zip herumgespielt, und ich hab Kompressionen von im Schnitt 1:0,8 gehabt. LZW Kompression hatte ich in meinen Überlegungen aber ohnehin schon immer mit in Betrachtung gehabt - also die angegebenen Zielgrößen sind als vor "naiver" Kompression zu verstehen die sowieso noch drauf kommt. Das Verhältnis von 1:0,8 weist zudem auch schon auf recht gute Entropie meiner Daten hin, so dass ich glaube nicht ohne Qualitätseinbußen mehr weit zu kommen - das muss nur auf geschickte Art und Weise passieren nun.

Die erste Koordinate von 32 auf 16 Bit zu reduzieren ist alledings schon mal eine gute Sache! Fast schon zu offensichtlich um es nicht schon gemacht zu haben... Rettet nicht den Tag, aber Kleinvieh macht auch ne Menge Mist :)

Grund der Aktion: Aus den Kurven wird nachher ein Bild rekonstruiert. Wenn diese Rekonstruktion als JPEG auf 90% Qualität gespeichert kleiner ist als meine Pfade, dann steh ich relativ dumm da ;) Und bislang produzier ich selbst nach 7zip Kompression noch größere Files als JPEG. Nicht arg viel, aber je nach Inhalt schon merklich.

PS: Mühelosigkeit beim Lesen/Schreiben ist hier nur wünschenswert, steht aber eher hinten in der Wichtigkeitsliste. Bytegrenzen pro Punkt wären schon prima, ansonsten bin ich da flexibel.

[himitsu]

Zitat:

Bei den Farben wäre das sogar vertretbar, bei den Normalen schon recht schmerzhaft (da diese eh in den meisten Fällen nur -8..8 sind, aber die seltenen größeren recht wichtig sind), bei den Koordinaten schon unbrauchbar. Letzteres vorwiegend weil sich der Fehler beim 10. Punkt schon ziemlich übel aufaddiert hat, im schlimmsten Fall eben 10 Pixel vom Zielort weit weg. Das geht leider garnicht.

wenn du beim Erzeugen der Liste diese Abweichung mit einrechnest, dann hebt sich das wieder auf und hat dann eine maximale Abweichung von 3 pro Wert.

[Medium]

Das meinte ich mit

Zitat:

Zitat von Medium

Wobei... man könnte bei den Koordinaten noch bei der Differenzbildung dem Aufaddieren von Fehlern entgegenwirken wenn man's nicht ganz dumm anstellt.

:)

Ich hatte ein wenig gehofft, jemand würde ein mathematisches Verfahren kennen mit dem sich solche Punktreihen effizient darstellen ließen. Ich hab ja schon an Fourierdeskriptoren gedacht, und dann davon nur "untere" Koeffizienten. Die Implementierung ist allerdings mittelmäßig einfach - steht aber fürchte ich ohnehin an - aber das Problem an der Stelle ist eher, dass die am besten mit geschlossenen Figuren arbeiten. Ich hab dagegen ja eher lange dünne Strecken, die bei Reduktion auf untere FD-Koeffizienten stark gestaucht würden, da eben diese Geradenähnlichkeit hohe Koeffs stark werden lässt. Damit handel ich mir also letztlich unglaubliche Fehler ein :?
Die Krux ist, dass sowohl offene als auch geschlossene Kurven auftauchen, wobei die offenen im Schnitt einen Anteil von rund 70% haben. (Ich betrache "geschlossen" schon als Figur der man grob einen Radius zuordnen kann, wobei die Figur einen größeren Teil dieses Umkreises füllen würde. Ein L z.B. würde ich als geschlossen ansehen, nicht aber wenn der senkrechte Strich 10x größer als der waagerechte ist. Mal so als Beispiel. Ist etwas schwammig...)

Ich hab ja schon stark reduziert indem ich nur Punkte des Ausgangspfades nehme an denen sich die Tangente stark ändert, und nachher mit Splines rekonstruiere. Aber dat langt noch nich wie mir scheint. Einfach hier und da Bits abschnibbeln scheint langsam an seine Grenzen zu kommen fürchte ich. Ich geb auch gerne zu, dass das nicht gerade ein Thema für zwischen Kaffeetasse und Mittagspause ist - aber ich komm da einfach nicht auf die zündende Idee.

[himitsu]

Du könntest die Punkte/Abstände doch auch etwas expotentiell/logarithmisch speichern?

Also insgesammt ein kleiner Datentyp, welcher um Nahbereich genauer ist und bei größerer Entfernung ungenauer wird.
Da hast du dann weniger Bits, und hast dennoch die Möglichkeit auch mal größere Abstände zu speichern

Und das mit dem Integer vor jeder Reihe ...
Ändert sich denn das Maß?
Also bleibt der Aufbau der Reihen gleich?
Wenn, dann könntest du doch nur am Anfang der Datei speichern, wie groß jeder Typ der Reihen ist und das dann nicht jedesmal extra nochmal davorsetzen.

[Medium]

Zitat:

Zitat von himitsu

Du könntest die Punkte/Abstände doch auch etwas expotentiell/logarithmisch speichern?

Hatte ich für die Normalen sogar schon mal angedacht, da diese eher klein ausfallen! Grundproblem war hier nur wieder, dass dieses Sparen von 2 Bits in einem Punkt-Block keine Bytegrenzen mehr hervorbringt. D.h. ich muss erst noch irgendwie sonst 6 Bits einsparen damit's nicht GANZ so unschön wird. Es soll ja auch noch in vertretbarer Geschwindigkeit auslesbar sein, und nicht 20 mal shiften pro Punkt erfordern :stupid:.
Bei den Koordinatendifferenzen macht's leider keinen Sinn mehr, da die ziemlich gleichmäßig auf dem Intervall verteilt sind.

Zitat:

Und das mit dem Integer vor jeder Reihe ...

Das ist immer ganz individuell. Aber das bringt mich dennoch auf eine Idee! Quasi RLE in groß: Ich sortiere die Reihen nach Länge, schreibe einen Wert wie viele Reihen nun folgen, und danach wie viele Punkte die haben. Dann einfach die Reihen hintereinander weg kritzeln bis zur nächst größeren Länge. Das ist schon mal nett! Das spart gerade bei komplexeren Dingen schon wieder einiges ein. Cool!

[Hybrid666]

das ganze vielleicht noch mit einem Huffman Baum komprimieren? Nur so eine idee. Am besten testest du es mit ein paar fällen und speicherst dann die bitbelegungen in deinem programm und nutzt konstant das, das spart dir das speichern der pfade in der datei. Ist zwar leicht ineffizienter, sollte aber trotzdem noch eine gute komprimierung hinbekommen.

Ich kann dir gerne ein Beispielprogramm zukommen lassen, das ist allerdings von der uni aus in ada geschrieben aber sehr gut kommentiert.

MfG