Pfiffiges Speicherformat für Punktlisten gesucht

[Medium]

Einen Huffi hab ich hier auch noch rumliegen. Sollte ich mal für meine Multimedia Vorlesung basteln. Allerdings vermute ich stark, dass Huffmann und LZW hier ähnlich effizient sind. Sehr stark sogar :). Die optimale Kompression soll wohl arithmetische sein, das Problem dabei ist nur dass die Implementierung idR nur heftigst ineffizient ist. Ich plane schon damit nachher 25x pro Sekunde so ein 1000-Pfade-Bild zu lesen, dekomprimieren, zeichnen und anzuzeigen. Bin ich noch weit von weg und ist eher zweitrangiges Ziel, aber arithm. Kompression haut da doch zu sehr in die Kasse.
Wie gesagt: Entropiekodierung setze ich ohnehin als letzten Schritt voraus. Mir geht's jetzt noch darum die "roh"-Listen mit im Zweifel verlustbehafteten Verfahren klein zu kloppen.

[himitsu]

Zitat:

Zitat von Medium

Entropiekodierung setze ich ohnehin als letzten Schritt voraus. Mir geht's jetzt noch darum die "roh"-Listen mit im Zweifel verlustbehafteten Verfahren klein zu kloppen.

Vergiß aber nicht, daß dafür auch einige Voraussetzungen nötig sind, um überhaupt noch eine "gute" Komprimierung zu erreichen.
Wenn du pech hast, dann optimierst du die Daten jetzt so gut, daß am Ende alles so schlimm aussieht, daß die Entropiekodierung viel weniger komprimieren kann und dann ganz am Ende sogar wieder mehr Daten rauskommen.
(versuche mal eine komprimierte Datei weiter zu komprimieren ... z.B. JPeg und Zip)

[Blup]

Daten "Vorzukomprimieren" und dann erneut durch einen anderen Algo zu komprimieren ist meist nicht effizient.
Sinnvoller ist es die Daten vor dem Komprimieren zu sortieren, daß gleiche Daten hintereinander liegen.

Ich stelle mir das im Prinzip so vor:

Delphi-Quellcode:

TPunkt: record
  x, y: Word;
  dx, dx: Byte;
  Color1, Color2: TColor;
end;

PunktListe: array of TPunkt;

i := Length(PunkteListe);
Stream.Write(i, SizeOf(i));

for i1 := 0 to SizeOf(TPunkt) - 1 do
begin
  for i2 := 0 to High(PunktListe) do
  begin
    p := @(PunktListe[i2]) + i1;
    Stream.Write(p^, 1);
  end;
end;

Selbst wenn jetzt das High-Byte bei allen x/y-Werten Null ist, stehen diese Nullen hintereinander im Stream.
Damit wird selbst simple RLE-Kompression fertig. Man kann die Sortierung auch bis zur Bitebene treiben.
Wenn die Reihenfolge der Punkte egal ist, könnten auch diese sortiert werden.

[Medium]

Zitat:

Zitat von Blup

Daten "Vorzukomprimieren" und dann erneut durch einen anderen Algo zu komprimieren ist meist nicht effizient.

Stimmt durchaus auch. Es wäre dann im Einzelfall nachher abzuwägen ob sich dieser Schritt überhaupt noch lohnt. Bislang bin ich noch nicht ganz da "von Hand" besser als die gängigen Algos zu komprimieren :)

Die Sortierung nach Byte-Order ist garnicht mal verkehrt, eben gerade weil doch einiges an 0-Bytes an gleichen Stellen vorkommt. Ähnlich macht's JPEG ja auch - wenn auch in ganz anderem Zusammenhang. Mal schauen wie ich das nun meinen C#-Klassen beibringe =]
Die Punkte selbst sind leider in fester Reihenfolge, da kann ich auf keinen Fall drin rumwurschteln. Aber die Kombi aus o.g. Sortieren nach Punktanzahl, und das Schreiben nach Byte-Order zusammen könnte sowohl von vorne herein etwas sparen als auch die Komprimierbarkeit schön steigern. Ich glaub das ist erstmal ein guter Plan für den Feierabend, joa. Bin gespannt wie weit ich damit runter komme!