Moin,
Nachdem das Thema kurz in der Shoutbox aufgetaucht ist und ich einige gute Hinweise bekommen habe wie man ein solches Problem angehen könnte, habe ich mich hingesetzt und eine (mehr oder minder) funktionierende Lösung gebastelt.
Was kann das Skript:
Es zerlegt Bilder in einfarbige Rechtecke die in einer gewissen Reihenfolge übereinandergestapelt werden und im Endeffekt eine verlustfreie Repräsentation des Bildes liefern.
Vorgehensweise:
1. Zähle die Farben im Bild
2. Erstelle für jede Farbe eine "bit"Map (also ein 2D Array aus 0 und 1) in derselben Größe wie das Bild (ab hier Layer genannt).
3. Erstelle aus den Layern eine 012Map (0 = darf nicht überzeichnet werden, 1 = darf überzeichnet werden, 2 = MUSS überzeichnet werden) für jede Farbe.
4. Erstelle aus jeder 012Map eine möglichst minimale Dekomposition
5. Stapel nun alle Dekompisitionen (jeweils korrekt gefärbt) übereinander et voilà, das Originalbild entsteht wie durch Zauberhand.
Das Problem ist nicht die Vorgehensweise ansich, sondern, dass es viele Schritte gibt die keine "schnellen" Lösungsalgorithmen erlauben, oder Schritte bei denen man eine Lösung nicht auf Optimalität prüfen kann ohne alles durchzuprobieren (brute Force).
Schritt 3: Layer pro Farbe -> 012Map pro Farbe
- Klingt als könnte hier nichts schiefgehen, aber welche Reihenfolge der Layer ist denn nun optimal?
- Bei einem 8 Farben Bild wären das schon 8! = ca. 40.000 Möglichkeiten, die will man nicht alle durchprobieren.
- Zur Optimierung wird hier eine Startlösung verwendet und immer wieder 2 Layer vertauscht, wenn das etwas bringt -> weiter, wenn nicht -> zurücktauschen.
Schritt 4: Dekomposition der 012Map
- Es gibt oft keine eindeutige Lösung, das ist super, weil es reicht "eine" optimale Lösung zu finden, aber woher weiß man ob die Lösung optimal ist?
- Wird durch glorifiziertes Ausprobieren gelöst (genau wie der vorherige Teil)
Die Methode ist relativ langsam (vllt in C++ umschreiben, aber dafür bin ich jetzt zu faul), für kleine Sprites mit wenigen Farben ist sie aber nützlich 
Da ich nicht nochmal 50 Seiten schreiben will (das Skript zum Programm hat ja schon einige wenige Zeilen) gibt es hier einfach das Skript zum Ausprobieren. Wenn Fehler/Fragen/Anregungen/etc. auftauchen, her damit 
PS: Es ist Absicht, dass Layerweise gearbeitet wird (also 1 Layer/Farbe) und die Rechtecke nicht vollkommen z-Unabhängig sind, so kann man "1x Farbe setzen -> 10 Rechtecke Zeichnen, 1x Farbe setzen -> xyz Rechtecke Zeichnen" und muss nicht für jedes Rechteck den Farbwert einzeln speichern (obwohl er der Einfachheithalber angehängt wurde)
lg
M