24bit RGB nach 8bit indexed color konvertieren

[OldGrumpy]

Hallo zusammen,

ich suche ein paar Anregungen und Tipps zu obigem Thema. Es geht darum, eine Anzahl Pixel (RGB, 24 bpp) möglichst effizient umzurechnen in eine angenährte 8-Bit-Darstellung inkl. entsprechende Farbtabelle. Es fallen also folgende Aufgaben an:

- Ermittlung der Anzahl Farben (IMHO trivial)
- Ermittlung der 256 "besten" Farben (also die Farben, mit denen die meisten RGB-Pixel direkt ersetzt werden können und/oder am wenigsten Farbverfälschungen auftreten)
- Erstellen der 8-Bit-Colortable und 8-Bit-Bitmap (wiederum relativ trivial)

Wie die Liste schon zeigt, bereitet mir vor allem der mittlere Schritt einiges Kopfzerbrechen. Für jegliche Tipps (und ggf. Erfahrungswerte) bin ich herzlich dankbar! Google hab ich schon etwas gequält, aber nichts wirklich brauchbares rausquetschen können. Ist vermutlich nicht mein Tag *g*
Hier im Board hab ich nur was zur Umrechnung in Graustufen gefunden, mir geht es aber um eine adaptive Farbtiefenreduktion.

Nachtrag: Ich brauche keinen fertig vorgekauten Code, eher einen Algorithmus :) Daher auch die recht allgemeine Beschreibung ohne Code, der würde hier eh nichts zur Sache tun.

[Muetze1]

Schonmal in efg's ComputerLab geschaut?

[Flocke]

Ich hab's vor gut 10 Jahren mal so gemacht:

Wir interpretieren den RGB-Farbraum als Quader mit 3 Achsen von 0 bis 255 und wollen diesen Quader so in 256 Unterquader aufteilen, dass in jedem möglichst gleich viele Einzelfarben der Bildpunkte liegen. Dazu gehen wir wie folgt vor:

1. Zu einem Quader merken wir uns jeweils den Bereich von-bis auf der R-, G- und B-Achse.
2. Beginne mit dem einen Quader (0-255,0-255,0-255).
3. Suche den flächenmäßig größten Quader. Hat dieser die Größe 1, dann springe zu Punkt 6.
4. Teile diesen Quader entlang seiner längsten Achse so auf, dass möglichst gleich viele Farben in beiden Hälften sind. Geht dies nicht (alle Farben gleich), dann reduziere diesen Quader auf diese eine Farbe und mache mit Punkt 3 weiter.
5. Solange wir weniger als 256 Quader haben, mache mit Punkt 3 weiter.
6. Wir sind fast fertig: jetzt entspricht jeder Quader einem späteren Paletten-Eintrag.
7. Ermittle jetzt für jeden Quader den wirklichen mittleren Farbwert der Einzelfarben, die darin liegen. Bei diesem Schritt kann man auch direkt die 256-Farb-Bitmap erstellen, da der Quader-Index ja dem späteren Paletten-Index entspricht.

Ist nicht meine Idee, allerdings weiß ich nicht mehr, wo ich den Algorithmus seinerzeit gefunden habe.

[DerDan]

Hallo,

als ersten Schritt würde ich noch das Bild auf Farben untersuchen, die nur ein paar Pixel oft vorkommen.

Also eine Statistik wie oft jede Farbe vorkommt. und diese "seltenen" Farben möglicht hier schon in "öfter" vorhandene, ähnliche
Farben ummappen. Auch würde ich Farben, die nur leicht von Grau abweichen auf Graue Farben mappen. Also schon mal in der vollen Farbtiefe eine Reduzierung der Anzahl Farben vornehmen.

Den Rest machst du wie Flocke beschrieben hat.

Ich hab mich mit dem Thema auch schon auseinander setzen müssen. Alle fertigen Grafikprogramme haben hier nicht optimal funktioniert.
Vor allem falls du noch transparente Bereiche hat wird es übel und du musst selber was machen.

Mich würden deine Ergebnisse sehr interessieren.

mfg


DerDan

[OldGrumpy]

Mit Transparenzen hab ich in dem Zusammenhang nicht zu tun, es geht einfach darum, ein File das in zwei Formaten vorliegen kann (einmal mit RGB 24bit oder mit 8bit plus Indextable) auch wahlweise wieder in beiden Formaten abspeichern zu können. In den allermeisten Fällen werden vermutlich eh keine 256 verschiedenen Farben vorliegen, aber wäre ja auch extrem doof wenn sowas mal vorkommt und das Speichern nicht klappt. Bissl Komfort darfs schon sein :) Grautöne und grauähnliche Farben kommen dabei eher nicht vor, mal sehen was mein Statistiker (ich liebe lustige Toolnamen) bei meinen Samplefiles so auswirft.

Heissen Dank auf jeden Fall für alle Anregungen, ich werd mal was zusammenbasteln.

[Flocke]

Kleiner Nachtrag: mir ist aufgefallen, dass der von mir beschriebene Algorithmus suboptimal arbeitet. Hier die verbesserte Version:

1. Zu einem Quader merken wir uns jeweils den Bereich von-bis auf der R-, G- und B-Achse.
2. Beginne mit dem einen Quader (0-255,0-255,0-255) kleinsten Quader, der alle vorhandenen Farben umschließt.
3. (Hier beginnt die Schleife) Suche den flächenmäßig größten Quader. Hat dieser die Größe 1, dann springe zu Punkt 6.
4. Teile diesen Quader entlang seiner längsten Achse so auf, dass möglichst gleich viele Farben in den beiden entstehenden Hälften sind. Geht dies nicht (alle Farben gleich), dann reduziere diesen Quader auf diese eine Farbe und mache mit Punkt 3 weiter. Achte darauf, evtl. Lücken zwischen zwei benachbarten Farben aus dem Ergebnis auszuschließen bzw. die beiden kleinsten Ergebnisquader zu wählen.
5. Solange wir weniger als 256 Quader haben, mache mit Punkt 3 weiter.
6. (Hier endet die Schleife) Wir sind fast fertig: jetzt entspricht jeder Quader einem späteren Paletten-Eintrag.
7. Ermittle jetzt für jeden Quader den wirklichen mittleren Farbwert der Einzelfarben, die darin liegen. Bei diesem Schritt kann man auch direkt die 256-Farb-Bitmap erstellen, da der Quader-Index ja dem späteren Paletten-Index entspricht.