Hallo zusammen Ich möchte Daten mittels RLE etwas komprimieren. Nun versuche ich dazu, einen Algorithmus zu schreiben welcher mir ein Array mit Bytes mittels RLE komprimiert. Dazu habe ich folgende Seite gefunden: http://www.gabotronics.com/tutorials/run-length-encoding-for-lcd.htm Dort wird das vorgehen eigentlich gut beschrieben: - Nimm zwei bytes - sind diese gleich? --> Ja: gib beide aus zähle wie oft die gleichen bytes kommen. gib diesen wert aus nimm wieder zwei bytes... prüfe... --> Nein: ... Nun die struktur ist dann folgende: 0x01 0x04 0x05 0x05 0x07 Folgend zweimal die gleichen Bytes aufeinander, so beschreibt das dritte wie oft das vorangegangene nun kommt. Bsp: 0x05 0x05 0x07 An dieser stelle kommt nun 7mal ein 0x05 0x01 0x04 Hier steht tatsächlich nur 0x01 und 0x04 Soweit so gut... Was ist nun aber, wenn ein byte mehr als 255 mal aufeinander folgt? Wie sieht es dann aus?
Gast
#3966915
>Was ist nun aber, wenn ein byte mehr als 255 mal aufeinander folgt?
Dann machste halt zwei Häppchen draus. Was anderes
bleibt doch gar nicht über.
Gast
#3966918
>Wie sieht es dann aus?
0x05 0x05 0xff 0x05 0x05 0xff ?!
(für 510 mal 0x05 hintereinander)
Außerdem kann man sich überlegen wie 0x05 0x05 0x00 und 0x05 0x05 0x01
behandelt.
Schlaumeier schrieb: > 0x05 0x05 0x00 Sowas kann nicht vorkommen in einer RLE komprimierten Datei... Schlaumeier schrieb: > 0x05 0x05 0x01 Dies ebenfalls nicht. Da dies bedeuten würde das 0x05 einmal vorkommt. Dan würde jdeoch einfach nur 0x05 stehen... Kannst du deine Idee etwas genauer erläutern? holger schrieb: > Dann machste halt zwei Häppchen draus. Was anderes > bleibt doch gar nicht über. Perfekt!
Du kannst da ganz nach Belieben dein eigenes Süppchen kochen. 0x05 0x05 0x00 macht ja eigentlich keinen Sinn, könnte aber eine Sonderbedeutung einnehmen. Könnte z.B. heissen, 0x05 kommt öfter als 255 mal hintereinander. Und wie oft steht dann z.B. im nachfolgenden 16-bit Wert. 0x05 0x05 0x00 0x20 0x22 hiesse dann also, dass 0x05 0x2022 (8226) mal wiederholt wird... und 0x05 0x05 0x01 0xff 0xff 0xff 0xff könnte z.B. für 4 Gigabytes 0x05 stehen...
Gast
#3967011
Holger Krähenbühl schrieb: > Sowas kann nicht vorkommen in einer RLE komprimierten Datei... In der Variante wie du es beschrieben hast nicht. Aber wenn das Protokoll noch nicht fest steht (weil du Einfluss auf Encoder und Decoder hast), kannst das das ausnutzen, um noch besser zu komprimieren: Dann bedeutet der Wiederholungszähler=n nicht n mal wiederholen, sondern n+2 mal wiederholen. Damit kannst du die Brocken um 2 bytes länger machen, und wenns gut läuft brauchst du am Ende weniger Brocken.
Übrigens kann es sich lohnen, darüber nachzudenken, welche Daten man zu komprimieren hat. Beispiel: es handelt sich um Bilddaten im RGB 5:6:5 Format. Da hat jedes Pixel 16 bit. Eine grüne Linie oder Fläche sähe z.B. so aus: 0x07E0 0x07E0 0x07E0 0x07E0 0x07E0 (...) Byteweise mit obigem Algorithmus nicht zu komprimieren, da keine gleichen Bytes aufeinanderfolgen. Als 16-bit Werte betrachtet allerdings schon...
Joe F. schrieb: > Byteweise mit obigem Algorithmus nicht zu komprimieren, da keine > gleichen Bytes aufeinanderfolgen. > Als 16-bit Werte betrachtet allerdings schon... Vielen Dank für deinen Hinweis! Gefällt mir sehr gut! Es handelt sich bei meinen Daten in der Tat um BMPs im RGB 565 Format. Dazu muss ich allerdings erstmal den BMP Header auslesen um zu wissen, ab wo die eigentlichen Daten beginnen. Den Header kann ich ja dann als 8bit RLE kodieren. Dazu könnte ich im ersten byte die Startposition der 16bit RLE Daten definieren.
wenn der header keine ungerade byte anzahl hat, wuerde ich mir diesen stress nicht geben. der header ist im vergleich zum rest sehr klein, einfach alles mit 16bit komprimieren...
Joe F. schrieb: > wenn der header keine ungerade byte anzahl hat, wuerde ich mir > diesen > stress nicht geben. der header ist im vergleich zum rest sehr klein, > einfach alles mit 16bit komprimieren... Das ist meine sorge... eine ungerade anzahl bytes...
Gast
#3967093
Wenn viele einfarbige Flächen vorkommen kann es lohnen vor der Kompression zeilenweise zu verXORen. Schau dir auch mal die Kompression vom LBM Format an.
angenommen das ganze bild ist eine einzige farbflaeche, dann ergibt zeilenweises xor doch lauter nullen. wie kommst du denn dann auf die urspruengliche information zurueck?
Gast
#3968586
Joe F. schrieb: > angenommen das ganze bild ist eine einzige farbflaeche, dann ergibt > zeilenweises xor doch lauter nullen. wie kommst du denn dann auf die > urspruengliche information zurueck? Naja, die erste Zeile muss man schon ungeXored speichern (gäbe ja auch keine vorhergehende Zeile mit der man verknüpfen könnte). Dann schaut das so aus: Originalbild:
1 | |
2 | |
3 | |
4 | |
Sukzessive EOR-Verknüpfung der Zeilen mit der jeweils diekt darüberliegenden Zeile:
1 | |
2 | |
3 | |
4 | |
Beim entpacken läuft's halt andersherum:
1 | |
2 | |
3 | |
4 | |
Antwort schreiben
Bitte melde dich an, um einen Beitrag zu schreiben.