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.