Einfache Bildkomprimierung für Mikrocontroller

Ist doch prima für RLE - fast nur eine Farbe.

Verlustbehaftet oder verlustfrei?

Ein sehr einfaches Verfahren für verlustbehaftete Komprimierung wird bei 
GPUs angewendet, für Texturkompression. Schau dir mal die Verfahen 
DXT1-DXT5 an [1]. Vielleicht wäre das ja etwas für dich. Die 
Dekompression ist praktisch trivial und Encoder gibt's schon fertig.

[1] https://en.wikipedia.org/wiki/S3_Texture_Compression

Holger Krähenbühl schrieb:
> Lässt sich dies verhältnismässig einfach auf einem AVR / STM
> implementieren?

Der bei GIF verwendete Kompressionsalgorithmus (LZW) lässt sich schon 
einfach implementieren, er braucht allerdings zur Laufzeit 10 Kilobyte 
RAM (grob geschätzt) für das Wörterbuch. Das könnte man durch eine 
eigene Implementation eines Encoders zwar beliebig beschränken, 
allerdings hätte das wiederum negativen Einfluß auf die 
Kompressionsrate.

Aber wenn man eh schon dabei ist einen eigenen Encoder zu schreiben, 
dann kann man eigentlich auch gleich mal andere Verfahren testen. 
Rangecoding zum Beispiel. Oder "Pucrunch" (LZ77+RLE). Auch wenn sich 
diese Algos normalerweise nicht für Images anbieten so könnten sie - dem 
Histogramm deines oben geposteten Bildes nach - in deinem Fall durchaus 
brauchbare Ergebnisse liefern, zumindest nach einer Farbquantisierung. 
C-Quellcodes sollten sich leicht ergoogeln lassen, und von Pucrunch 
hatte ich auch mal irgendwo eine Assemblerversion für ARMs gesehen.

Rufus Τ. Firefly schrieb:
> Ich interpretiere die Frage des Threadstarters so, daß er gerne
> (irgendwo anders erzeugte) Bilder auf einem µC dekomprimieren möchte,
> also keinen Encoder, sondern einen Decoder benötigt, der Bilder aus
> dem Flash-ROM auspackt.

Das Codebook braucht man natürlich auch zum Dekodieren...

Rufus Τ. Firefly schrieb:
> ...

Ist ja richtig, und war von mir auch so gemeint. Wie Drama sagte, der 
Decoder muss sich während des Entpackens das gleiche Wörterbuch anlegen, 
von daher hatte ich nicht auf sprachliche Exaktheit geachtet.

Für einen Überblick habe ich das obige Bild mal auf 256 Farben reduziert 
und als rawdump abgespeichert (256*3 Bytes Farbtabelle + 320*240 Bytes 
Indizes) um verschiedene Verfahren zu testen:

Originalbild, ungepackt: 77.568 Bytes
Arithmetic Coder (Order 0, adaptiv): 17.559 Bytes
RLE: 16.328 Bytes
LZW (12 Bit Wörterbuch): 16.198 Bytes
RLE+A.C.: 13.926 Bytes
PNG: 13.295 Bytes
Pucrunch: 13.199 Bytes
GIF: 12.342 Bytes

Anmerkungen:
- die sourcecodes für RLE, AC und LZW habe ich eben von 
http://marknelson.us/ geholt, Pucrunch von 
http://koti.kapsi.fi/a1bert/Dev/pucrunch/
- ob der Arithmetic Coder (immer noch) patentbelastet ist weiss ich net, 
aber der nahezu identische Rangecoder müsste frei verwendbar sein.
- den Speicherplatzbedarf (beim Entpacken) vom Pucrunch müsste man 
nachlesen. Dürfte aber nicht viel sein.
- der LZW hat beim testweisen entpacken nur einen Coredump produziert, 
und da ich keine Lust auf's Debugging habe werden wir wohl nie erfahren 
ob er korrekt gearbeitet hat. Eigentlich hätte ich ein Ergebnis ähnlich 
wie beim GIF erwartet. Naja, da muss man sich die Implementierung halt 
mal genauer anschauen.

So wie es aussieht scheinen RLE und RLE+RC brauchbare Lösungen zu sein; 
der Implementierungsaufwand ist gering und viel Speicher wird auch nicht 
benötigt. Für den RC mal nach dem carryless rangecoder von Dmitry 
Subbotin googeln. :)

Heatshrink scheint dahingehend entwickelt worden zu sein große 
Datenmengen (mehrere Megabytes) zu komprimieren. Man könnte es 
vermutlich für - die hier gegebenen - kleinen Datenmengen anpassen, aber 
bessere Ergebnisse als von den bereits erwähnten Verfahren würde ich 
nicht erwarten.

Ich habe das Bild jetzt mal noch mit LZO, Heatshrink und Exomizer 
getestet, und die Tabelle schaut nun so aus:

Originalbild, ungepackt : 77.568 Bytes
Heatshrink : 21.534 Bytes
Arithmetic Coder (Order 0, adaptiv) : 17.559 Bytes
RLE : 16.328 Bytes
LZW : (12 Bit Wörterbuch): 16.198 Bytes
LZO : 14.003 Bytes
RLE + AC : 13.926 Bytes
PNG : 13.295 Bytes
Pucrunch : 13.199 Bytes
Exomizer : 12.706 Bytes
GIF : 12.342 Bytes

- die Packer haben übrigens allesamt ihre jeweiligen default Parameter 
verwendet, da kann man möglicherweise noch ein bisschen was tunen. Aber 
Wunder würde ich dabei nicht mehr erwarten.
- beim Pucrunch habe ich jetzt gesehen: "Uses no extra memory in 
decompression."
- nach einem flüchtigen Blick in den Source: Der Decoder des Exomizers 
scheint im Wesentlichen zwei Arrays zu je 52 Bytes anzulegen


PS: Die bisherigen Verfahren sind allesamt verlustfrei, was für "Buttons 
mit Rahmen" sicherlich angemessen ist (da will man ja keine Artefakte 
sehen). Für das schwarze Bild mit dem grünen Dingsbums könnte man aber 
auch ruhig JPEG o.a. verwenden. Hast du da mal nach einer Bib für 
eingebettete Systeme gesucht?

PPS: Der Exomizer ist gewissermaßen der jüngere Bruder vom Pucrunch. 
Beide waren mit dem Hintergedanken entwickelt worden die Daten auf den 
alten Commodore Homecomputern entpacken zu können - also auf dem C64 :]
Von daher sollten sie für MCUs eigentlich sehr gut nutzbar sein.

Holger Krähenbühl schrieb:
> Das Problem ist jedoch, dass diese gewaltig viel Speicher benötigen.
> Gibt es einfachere komprimierungsverfahren, welche einfacher auf einem
> AVR oder STM32 implementiert werden können? Es muss nur dekodiert
> werden.
Wozu muss man die Bilder eigentlich komprimieren? Eine 2GB SD-Karte 
kostet doch fast nichts und sollte auch ohne komprimierung reichen

Wenn die Bilder auf den internen Speicher sollen, dann würde ich mal 
über Vektorgrafik nachdneken.

Holger Krähenbühl schrieb:
> Der Exomizer sieht nicht gerade sehr kompakt aus...

Naja, der Packer vielleicht nicht, aber das kann einem ja egal sein. Den 
Entpacker finde ich jedoch schon ziemlich kompakt. Hab' den Entpacker 
gerade mal testweise in einem C-Code genutzt (siehe Anhang), und das 
ging problemlos.

Problematisch dürfte dagegen sein, das der Exomizer soweit ich weiss 
nicht besonders schnell ist und bei manchen Files fehlerhaft arbeitet :/