Hi Leute,
ich bräuchte mal wieder eure genialen Ideen.
Es geht um die Entwicklung eines Optimeirungs-Algorithmus der zur Komprimierung von Bitmaps dienen soll. Ok, werden viele sagen, das gibts ja schon nimm doch JPEG, GIF oder RLE, aber das geht nicht. Hintergrund bei der Sache ist es nämlich das die Bitmaps, bzw. Fonts auf Embedded Controllern, sprich Mikrocontrollern, laufen soll. Aus diesem Grunde muß die Komprimierung so aufgebaut sein das sie sehr einfach und effizient auf diesen MCU's umzusetzen ist, und natürlich sehr Speichereffizient sein muß.
Nungut die grundlegende Speichermethode habe ich schon fertig entwickelt. Angenommen wir haben 4 farbige Bitmaps dann werden diese 4 Farben in jeweils 2 Bits codiert.
Also 00 = Farbe 1, 01 = Farbe 2, 10 = Farbe 3 und 11 = Farbe 4. Will man nun eine Bitmap mit 10x10 Pixeln speichern benötigt man unkomprimiert also 10x10 * 2 Bits = 200 Bits = 25 Bytes. Bei vielen solcher Bitmaps oder eben Zeichen in einem Font ist das zu speicherintensiv.
Als erstes dachte ich an einfaches RLE = Run Length Encoding, aber die herkömmlichen RLE Verfahren waren nicht sehr zufriedenstellend.
Ich bin dann auf die Idee gekommen zwei zusätzliche Bits als Run Lenght = Wiederholungszähler zu codieren.
Also zB. 01 für Farbe 2 und 01 für 2 mal. D.h. also
cc = Farbbits
rr = Wiederholungszähler
rr kann nun 00 für 1 mal Wiederholung, 01 für 2 mal, 10 für 3 mal und 11 für 4 mal Wiederholung stehen.
Angenommen wir haben nun 3 Pixel in Farbe 01 dann würden wir speichern 0111. Bei 5 Pixel dann eben 0111 0100 also 4 Pixel + 1 Pixel in 01 Farbe.
Es stellte sich nun raus das die Längenkodierung von 00 = 1x, 01 = 2x, 10 = 3x, 11 = 4x nicht IMMER die effizientes Form ist. In vielen Bitmaps war nämlich 00 = 1x, 01 = 2x, 10 = 4x und 11 = 8x viel besser.
Nun zum eigentlichen Problem. Man kann ja die Bitmapdaten im vornhinhei analysieren und die Längen mit gleichen Farben ermitteln, sozusagen eine Statistik über die Häufigkeiten wieviele gleichfarbige Pixel nacheinander in der Bitmap vorkommen.
Dies sähe zB. so aus:
Code:
1 = 36
2 = 89
3 = 40
4 = 171
5 = 50
6 = 24
7 = 89
8 = 11
9 = 54
10 = 4
11 = 51
12 = 3
13 = 58
14 = 2
15 = 47
16 = 6
17 = 19
18 = 0
19 = 20
20 = 0
21 = 3
In obiger Tablle sieht man das Pixellänge 1 36x vorkommt oder 6 gleichfarbige Pixel am Stück eben 24 mal vorkommen.
Diese Tabelle ist als vorhanden und soll nun als Input für die Optimierungs-Algorithmus dienen. Der Algo. soll ermitteln welche Längencodierungen für die Längenbits 00, 01, 10 und 11 die beste Komprimierung ergibt.
Logischerweise ist das Längenbit 00 immer mit Pixelanzahl 1 verküpft. Steht also in den komprimierten Bitmapdaten die Bits 0100 dann heist die setze 1 Pixel in Farbe 01.
Aufgrund obiger Tabelle sieht man das die Länge 4 sehr oft vorkommt, also wird sie direkt mit den Bits 01 verknüpft. Somit verbrauchen 4 Pixel gleicher Farbe nur 4 Bits in den komprimierten Daten. Zb. 4 Pixel in Farbe 10
würden demzufolge 10 01 codiert werden, 10 für Farbe und 01 für 4 mal.
Bleiben noch die Längenbits 10 und 11 übrig. Diese müssen nun eine länge zugewiesen bekommen aber so daß die höchstmögliche Kompressionsrate entsteht. Das muß als unser Algo. aufgrund obiger Tabelle ermitteln können.
Nochmal, angenommen die Längenbits sidn so codiert
00 = 1x
01 = 2x
10 = 4x
11 = 8x
und wir wollen 11 gleichfarbige 00 Pixel codieren, dann sähe das so aus:
00 11 00 01 00 00, -> Farbe 00 8x, Farbe 00 2x, Farbe 00 1x = 11x Farbe 00.
Verbrauchen tun wir 12 Bits für 22 Bits Farbinformation. Also schon fast 2 fache Komprimierung erzielt.
ABER ! angenommen in obiger Tabelle wäre in der Zeile 11, also bei 11 gleichfarbigen Pixeln die höchste Anzahl ermittelt worden dann wäre die Längencodierung von
00 = 1x
01 = 2x
10 = 4x
11 = 11x
viel viel effizienter. Denn nun sähe die gleiche 11 Pixel Codierung so aus:
00 11 -> Farbe 00 11x, also 4 Bits zu 22 Bits Farbinformation, was fast 6 fache Komprimierung ist.
Nun, d.h. abhängig von einer gegebenen Längen-Statistik soll die bestmögliche Längencodierung gefunden werden !!
Das ganze Verfahren läuft darauf hinaus das zu einem komprimeirten Font oder Bitmap eine kleine 4 Bytes große Längentabelle gespeichert wird. Diese ermöglicht es dann sehr sehr schnell diese Daten zu dekomprimieren und live als Pixel anzuzeigen.
Mathematisch könnte man das Problem so umschreiben:
Gegeben eine Tabelle wie die obige. Wähle die 4 Elemente aus die alle Elemente der Tabelle mit den wenigsten Additionen ermöglichen.
Ich hoffe das sich wenigstens einer mal dieses Problem anschauen wird
Gruß Hagen