Algorithmus Challenge

[negaH]

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

[kiar]

hallo hagen,

habe es mir angesehen, die herleitung ist schon genial, zumindest das was ich verstanden habe.

aber sicherlich, sind die die hier helfen könnten < 1% .

das wirst du schon selber machen müssen.

also,viel spass

raik

[Meisterschmied]

Hi negaH,

also, was mir ganz spontan zu dem Thema einfällt: Wir nehmen für 00 -> 1, da wir eins natürlich immer brauchen. Dann wählen wir den höchsten Posten aus und setzen ihn zu 01 (in unserer Liste die Nummer 4 mit 171 Treffern). Dann führen wir eine Analyse der mittleren Abweichung aus, nicht aber als Durchschnittswert, sondern als neue Liste. Dort wählst du wiederum den höchsten Posten aus und legst ihn bei 10 ab. Als vierten und letzten Posten führen wir folgende Analyse aus:

1) Welche Folgen lassen sich aus der Liste aus den drei berechneten Werten zusammensetzen (00+01; 00+10; 01+10; 00+01+10). Diese Streichen wir aus der Liste

2) Welche mittleren Abweichungen bei den Kombinationen (00+01; 00+10; 01+10; 00+01+10) in Listenform ergeben sich für die übrig gebliebenen Werte und durch welchen Wert würde dieser am Besten repräsentiert.

Das ist jetzt allerdings noch sehr grob. Es fragt sich außerdem, ob du nicht vielleicht mit drei Bits am Besten beraten bist. Wäre zumindest eine Überlegung wert.

Man kann dabei noch viele Parameter ändern, z. B. ob man die beiden größten Posten nimmt und dann die mittlere Abweichung berechnet. Das ist zudem auch mit Sicherheit nur eine schlechtere Näherungslösung und mir nur gerade in den Sinn gekommen. Ich werde mal eine Nacht drüber schlafen Auch müsste man nicht am Anfang den größten Posten nehmen, sondern vielleicht sehen, ob man nicht mit dem zweit- oder drittposten besser beraten wäre. Das ist allerdings eine Sache, die man für jedes Bitmap entscheiden müsste.

Ciao,

Wieland

[Meisterschmied]

Hi negaH,

also, ich hab zwei Nächte drüber geschlafen und bin, glaub ich, zu einem ganz interessanten Ergebnis gekommen.

a) Ich glaube dein Problem ist nicht exakt lösbar, zumindest nicht in vernünftiger Zeit. Dein Problem erinnert stark an Varianten des Travellers Problem. Von daher werden wir uns mit Näherungslösungen zufrieden geben müssen.

Ich würde das Problem wie folgt lösen:

Die 00 ist reserviert für 1, da wir auf jedem Fall alle Zahlen als Summe der Längenbits darstellen müssen. Für die Berechnung von 01 gehen wir wie folgt vor: wir gucken, bei welcher Kombination von (00 + 01) die größte Summe herauskommt. Wenn wir unsere Liste betrachten, wäre das folgendes: Wir fangen von oben an:

Würden wir für 01 := 2 setzen, bekämen wir eine Summe von den Posten 2 und 3 (00+01) zu 129. Setzen wir 01 := 3, bekommen wir als Summe der Posten 3 und 4 (00+01) 211. Und so weiter, der höchste Posten gewinnt. Es wäre in diesem Fall allerdings noch zu differenzieren, dass es im Allgemeinen am Besten wäre, wenn 01 > (00+01) gälte, daher dass z. B. 4 > 5 gilt. Als nächstes machen wir für 10 etwas ähnliches: Wir gucken, wann die Summe aus (10+00 und 10+01) mit 10+00 <> 01 am größten ist. Für 11 muss vor allem gelten, dass alle Zahlen in einem vernünftigen Zugriff liegen, aber da gibt es viele Möglichkeiten, dass zu gestalten, da wird dir schon was einfallen.

Hoffe, es hat dir weitergeholfen. Bitte poste mir mal (gern auch im PN), wie du das ganze nun wirklich umgesetzt hast. Würde mich sehr interessieren .

Ciao,

Wieland

[negaH]

Hi Meisterschied,

Ich habe es gelösst allerdings ganz anders. Das lag hauptsächlich daran das meine obige Problemstellung garnicht das eigentliche Ziel richtig treffen kann. Sorry, dafür das du dich so lange reingekniet hast.

Ich bin im Grunde auf exakt die gleiche Lösung wie du gekommen, war aber am Anfang noch der Meinung die maximal beste Lösung finden zu können, bzw. das eine der gefundenen Lösungen (falls es mehrere gibt) immer das Maximum darstellt.

Allerdings, nur auf grund einer statistischen Tabelle die NICHT auch das tatsächliche sequentielle Auftreten der einzelnen Längen in den Bitmaps berücksichtigt, kann die gefundene Lösung garnicht die beste sein !!

Soll heisen: wird nur mit obiger Tabelle nach dem besten "Pfad" gesucht so beträfe die Lösung alle Bitmaps mit gleicher Längenstatistik im Durchschnittlichen. Es ist aber entscheidend, ausgehend von den realen sequentiellen Längenverteilungen in den Bitmaps, die maximal beste Komprimierung zu erreichen.
Dies kann nur funktionieren wenn man auch immer im Optimierungsverfahren die tatsächlichen Bitmapdaten berücksichtigt, und eben nicht nur eine Statistik.

Die Statistik und dein Algo. können aber dazu benutzt werden meinen derzeitigen Suchalgorithmus zu beschleunigen. D.h. über deinen Algo. kann man eine Vorabschätzung errechnen mit welchen Suchmustern der eigentliche Suchalgo. am besten beginnen soll.

Gut, meine derzeitige Lösung, könnte man als Brute Force Suche mit vorzeitigem Abbruch bezeichnen. D.h. als erstes wird obige Längentabelle ermittelt. Somit kennen wir die Gesamtmenge aller Elemente die für die späteren Kombinationen 3 aus x nötig sind.
Nachdem nun die obigen Daten erfasst wurden wird JEDE Kombination anhand einer Testkomprimierung der Daten durchgespielt. Es wird also die tatsächlich mögliche Komprimierungrate der Daten mit zu jeweils jeder möglichen Kombination ermittelt. Allerdings, übersteigt diese aktuell kummulierte Größe der bisher komprimierten Daten die Größe der aktuell besten Komprimierung wird die Testkomprimierung abgebrochen. Diese Abbruchsbedingung wird zur durchschnittlichen Komprimierungsgröße jedes einzelnen Zeichens ermittelt.

Dieses Verfahren erscheint im ersten Moment sehr un-optimial, aber leider kann es anders garnicht funktionieren. Denn wir müssen, um die MAXIMAL beste Komprimierung zu ermitteln tatsächlich mit den Life-Daten viele Testkomprimierungen durchführen.

Nungut, es zeigte sich das mein Mini-Huffman-RLE Verfahren die Fontdaten ca. 30-60% im Durchschnitt komprimiert, und teilweise sogar weit über 200%.

Dabei ist zu bemerken das die unkomprimierten Daten ja nur 2-16 Kb groß sind und diese Daten per simplen RLE mit 4 Bytes Lookuptable so "stark" zu komprimieren ist schon enorm. Auf alle Fälle ist diese Form der RLE Komprimeirung besser als die Windows Bitmap RLE Komprimierung oder die PNG RLE Komprimierung, das habe ich getestet. Viel wichtiger war aber der Punkt das meine Fontdaten sehr variable Farbtiefen besitzen können, also 1,2,4,8,16,32,64,128,256 Farbenfonts ermöglichen. Bei diesen Anforderungen sind die anderen RLE Verfahren einfach zu kompliziert und erbrachten zu schlechte Kompressionsraten. Desweiteren ist die Dekomprimierung bei meinem RLE enorm effizient und einfach auf Embedded Controllern umzusetzen. Man benötigt auch nur 4 Bytes an zusätzlicher Lokkuptabelle mehr, als bei unkomprimierten 1 zu 1 Bitmapfonts. In fact, die komprimierten Fonts werden durch die eingesparten Speicherzugriffe im Vergleich zu unkomprimierten Fonts sogar noch wesentlich schneller angezeigt. Statt für 32 gleichfarbige Pixel eines 4 Farbfontes 8 Bytes aus dem langsammen Flash zu lesen, werden bei komprimierten Fonts im Bestfall nur 0.5 Bytes aus dem externen Speicher gelesen. Die Durchschnittliche Kompressionsrate für die Fonts die ich benötige betrugt pro Zeichen 60%, also über die Hälfte der Datenmenge wurde eingespart.

Soweit erstmal meine erzielten Resultate.

Gruß Hagen