Farbsuche in Palette (nearest Color Index)

Hallo
Nur kurz eine Frage: Gibt es eine effizientere schnellere Methode, Farben aus einer Farbpalette zu finden als durchiterieren und die Distanzvektoren zu vergleichen? Das Durchiterieren kann bei über 1000 Farben (16-Bit-Paletten) zuweilen schon recht lange dauern.

	if((color1 & 0xFF000000) == 0 && transparencyIndex >= 0) {
		return transparencyIndex;
	}
	int smallestError = Integer.MAX_VALUE;
	int currentError;
	int rc = -1;
	int color2;
	for (int n = 0; n < size; n++) {
		color2 = (int) palette.readColor(n);
		if (color1 == color2) {
			return n;
		}
		currentError = distanceSquared(color1, color2);
		if(smallestError > currentError) {
			smallestError = currentError;
			rc = n;
		}
	}
	return rc;
}

static int distanceSquared(int rgb1, int rgb2) {
	int rd = ((rgb1 >> 16) & 0xFF) - ((rgb2 >> 16) & 0xFF);
	int gd = ((rgb2 >> 8) & 0xFF) - ((rgb2 >> 8) & 0xFF);
	int bd = (rgb2 & 0xFF) - (rgb2 & 0xFF);
	rd = rd * rd + gd * gd + bd * bd;
	return rd;
}```
Ich hätte (bzw. habe) ja Google bemüht, aber ausser nach den Suchbegriffen im Titel wüsste ich nicht, wonach ich suchen sollte. Irgendwelche Ideen?

Sooo viel wird da ja nicht gemacht. Sicher dass nicht das “readColor” das Teuere ist? Was wird da gemacht?

Ansonsten wird die Luft wohl recht schnell dünn, wenn man nicht irgendeine Art der Sortierung/Ordnung (z.B. “Der Rotanteil wird immer größer” oder so…) oder bestimmte Diskretisierung annehmen kann…

Also man kann nicht ausschliessen, dass readColor dafür verantwortlich ist, es kommt auf das Farbmodell (also RGB, HSB, CMY usw) an. Ok, es müsste eigentlich auch readRGBA heissen. Aber im normalfall kommen da nur ints aus einem Array.
An der Stelle, wo es drauf ankommt (Image-Dithering), ist die Palette bereits nach Population der einzelnen Farben sortiert. Wenn aber bei einem 800 * 600 Pixel grossen Bild alle Farben rund 480 mal vorhanden sind, ist diese Sortierung für die Katz. Deswegen dachte ich, ob sich da vllt. irgendwelche Algos lohnen, die die Palette nach der Farbvektorlänge vorsortieren und man dann je nach Farbvrktorlänge der gesuchten Farbe vorwärts oder rückwärts sucht. Ein entsprechender Sortiervorgang dauert aber länger als das Suchen wie bisher. Was wären den da sonst noch für Diskretisierungen, die man annehmen könnte?

Evtl. kann es ja auch sein, dass für eine Floyd-Steinberg-Reduzierung mit Median-Cut von 77757 auf 2027 Farben bei 800*600 Pixeln ca. eine Minute durchaus ok sind und ich an Performance-Paranoia leide.
Für selbiges auf 50339 Farben (16-Bit-Palette) werden 8 Minuten benötigt, wobei die Erstellung der Palette schon 1 Minute in Anspruch nimmt. Der Diffuse-Algo ist dabei übrigens nicht so wichtig, er sorgt nur dafür, dass im Endresultat mehr Farben vorhanden sind, zumindest beim Median-Cut. Beim Popularity-Cut werden stets zwischen 64000 und 65536 Farben verwendet (bei dem konkreten Beispiel 64488) und 7 Minuten benötigt.

So der Experte bin ich da ja nicht, deswegen (wie immer) alles was ich sage mit vieeel Vorbehalt aufnehmen.

Den Floyd-Steinberg hatte ich nur einmal schnell runterimplementiert, aber üblicherweise geht es da ja gerade um wenige Ziel-Farben, deswegen ist die Suche eigentlich kein Problem. Wenn es aber „viele“ Ziel-Farben sind, kann das sicher schnell zum Bottleneck werden.

Mit der Diskretisierung meinte ich GROB sowas, wie dass man weiß, dass (nur um den Gedanken zu verdeutlichen!) die Zielfarben alle von der Form (10r, 10g, 10*b) sind, wobei r,g,b eben Werte zwischen 0 und 25 sind. Dann könnte man die „nächstgelegene“ Zielfarbe eben direkt berechnen, aus (R,G,B) = (234, 123, 45) würde einfach (r,g,b)=(23,12,4) => (230,120,40) (von der Frage nach Auf/Abrunden mal abgesehen). Aber wie wir alle wissen: Die Prämisse eines Satzes der Form „Wenn… dann könnte man einfach…“ ist NIE erfüllt :smiley:

Ansonsten gibt es ja doch die eine oder andere Datenstruktur, um schnell in einem 3D-Raum zu suchen (und das macht man ja, z.B. im RGB-Raum)…

( :stuck_out_tongue_winking_eye: )
und natürlich alles, was in Richtung Spatial- oder Locality Sensitive Hashing geht…

Unter nearest neighbo(u)r, closest match oder Voronoi Diagramm/Wigner-Seitz-Zelle könnte man möglicherweise etwas brauchbares finden. Ich habe eben einen flüchtigen Blick in Fast Algorithms for Nearest Neighbour Search geworfen, und da stand dies irgendwo in der Einleitung:

In dem Paper werden, laut Inhaltsverzeichnis, die Algos Partial Distance Search (PDS), k-Dimensional T rees (KDT rees), BBF-T rees and Variants, Metric (Ball) Trees, vp-T rees and Hybrid Sp-Trees, Voronoi Diagrams, Orchard’s Method, Annulus Method, AESA and LAESA, R-Trees, X-Trees, M-Trees, TV-Trees, SR-Trees and VA-Files, Locality Sensitive Hashing (LSH) und Navigating Nets and Cover Trees näher beleuchtet. Vielleicht ist da was brauchbares dabei. Klingt allerdings, als könnte das recht aufwendig werden… -_-

Ohhh, ja… klingt ganz schön aufwendig. So aufwendig, dass sich der Versuch, es zu implementieren, kaum lohnt, wenn man nicht mal weis, ob es dadurch schneller geht. Naja. Die lineare Suche klappt ja schon mal. Der Link zu dem PDF auf CiteSeer ist leider defekt oder muss man sich da anmelden?

Ich versuche das Ganze grade auf Swing umzubauen, aber da stören mich diese festgetackerten (immutablen) IndexColorModelle, was das Ganze nochmal verkompliziert.

Yo, ich würde mich da auch nicht groß einlesen wollen… Aber vielleicht findet man durch einen flüchtigen Blick auf bestehende Algos die eine oder andere Idee, die sich leicht verwenden lässt.

Was mir ad hoc einfällt:

  • gegeben sei eine nach RGB-Werten sortierte Farbpalette P und ein beliebiger RGB-Wert c.
  • gesucht ist dasjenige Element x aus P, das die geringste RGB-Distanz zu c hat
  1. finde mittels binärer Suche denjenigen Wert w aus P, dessen Rot-Wert demjenigen von c am nächsten kommt
  2. berechne die RGB-Distanz d zwischen c und w.
    These: Wir können unsere Suche nun auf diejenigen Werte aus P beschränken, deren Rot-Wert um höchstens d von c abweicht
  3. finde mittels binärer Suche die beiden Schranken
    3a) untere Schranke: der kleinste Wert aus P, dessen Rot-Wert >= c-d ist
    3b) obere Schranke: der größte Wert aus P, dessen Rot-Wert <= c+d ist
  4. suche linear in der beschränkten Palette

Im worst-case nützt einem das zwar nix, aber es schadet auch nicht viel. Im average-case könnte das hingegen schon ein bisschen was bringen.

PS: Beim CiteSeer ist über dem download-link des PDFs auch noch ein Link zur gecachten Datei (auf das PDF-Symbol klicken). Das tut’s in aller Regel.

Ohne die Referenzen alle durchgesehen zu haben: “Oft” geht es bei der Nearest-Neighbor-Suche um “hochdimensionale” Probleme (“Hoch” ist hier ein sehr dehnbarer Begriff. Ich stand kürzlich vor dem Problem, eine NN-Suche in einem 784-Dimensionalen Raum machen zu … müssen/wollen… und dann kam natürlich der http://de.wikipedia.org/wiki/Fluch_der_Dimensionalität und sagte: “In die FRESSE” :sick: ). Jedenfalls ist da oft von 10-20 Dimensionen die Rede, z.B. bei den M-Trees, Ball-Trees und Cover-Trees. (Und einige der Papers berichten ganz stolz von einer “Query Time die Linear mit der Anzahl der Dimensionen” ist - und im Kleingedruckten steht dann: “Joa, das Aufbauen dieser Datenstruktur benötigt aber eine Zeit, die exponentiell in der Anzahl der Dimensionen ist” :rolleyes: Bin dann beim Locality Sensitive Hashing gelandet, aber da dort “Wahrscheinlichkeiten” eine Rolle spielen, lautet das Zauberwort wohl schlicht mal wieder “Dimensionsreduktion”).
Wie auch immer…
…für 3D sollte der Aufwand ja noch vertretbar sein, bzw. auch welche der “Einfacheren” Datenstrukturen reichen… aber auch da müßte man sich ggf. erstmal reinfuchsen…

Du machst aber auch immer seltsame Dinge… Wie ist es denn ausgegangen? Lag die Laufzeit des Locality Sensitive Hashings im vertretbaren Rahmen oder sind beim Betrieb wieder Kaffeepausen angesagt, wie weiland beim C64? :slight_smile:

Joa, sollte man meinen. Aber sich wegen eines so „banalen“ Problems in irgendwelche abgespaceten Theorien reinfuchsen…? Man könnte erstmal schauen wie lange Matlab & Co bei einem konkreten Problembeispiel benötigen. Wenn die nicht wenigstens 20x so schnell sind wie der simple Ansatz, dann käme das Problem bei mir irgendwo weit nach hinten auf die Todo-Liste.

Obwohl es bestimmt ein interessantes Thema sein kann…

Ich hab jetzt nicht alles durchgelesen und vl ist diese Idee bereits gefallen,

3 Farbkanaele ist ja jetzt eigentlich auch nichts anderes wie 3 Dimensionen fuer Objecte. Wenn du deine Farbpallete nun als Punkte in einem 3D Raum betrachtest koennetest du ja dann um die 3D Punkte BoundingBoxen legen (theoretisch dann auch hierachisch zusammenfassen).
Um nun den naehesten Nachbar zu finden, musst du anfaenglich nur die naeheste BoundingBox finden und im Anschluss nur jene Punkte vergleichen die in dieser BoundingBox enthalten sind.

Damit wird die Komplexitaet nur beim Erstellen der Palette einmal gemacht und beim Suchen nach der Farbe muessen nicht mehr alle Farbe verglichen werden.

Lg
Amunra

Nun, man hat da ziemlich viele Tuning-Parameter (Anzahl Hashes, Art der Hashes, Radius der Suche…) und davon hängt natürlich die Laufzeit ab. Für bestimmte Fälle KANN es um Größenordnungen schneller sein, als eine lineare Suche, aber trotz allem ist es eben ein Verfahren, das nur mit einer bestimmten Wahrscheinlichkeit die NN findet. Und wenn man Ausreißer hat, werden die u.U. schlicht nicht gefunden. Hab’ mich dann aber auf andere Sachen konzentriert. Die 784 waren ein Extremfall, normal sollten es nicht mehr als vielleicht 10 oder 20 werden.

Ja, das ist ein bißchen Tricky am „Nächste Nachbarn“-Suchen: Nur Bounding Boxes reicht erstmal nicht. Wenn man eine Anfrage macht, ist die ja vielleicht geeeraaade so um 0.00001 außerhalb der BB, die den „Nächsten Nachbar“ enthält. Oder anders formuliert: Das Problem, die nächste BoundingBox zu finden ist dann das Problem :wink:

Naja, solange es entweder blitzschnell geht oder aber für mindestens eine Kaffeepause reicht ist ja alles in Ordnung. :slight_smile:

Ja, das ist ein bißchen Tricky am „Nächste Nachbarn“-Suchen: Nur Bounding Boxes reicht erstmal nicht. Wenn man eine Anfrage macht, ist die ja vielleicht geeeraaade so um 0.00001 außerhalb der BB, die den „Nächsten Nachbar“ enthält. Oder anders formuliert: Das Problem, die nächste BoundingBox zu finden ist dann das Problem ;)[/QUOTE]
Das erinnert mich jetzt stark an den Median Cut vom alten Heckbert. Den hatte ich vor gefühlten 30 Jahren mal mit Bounding Boxen implementiert. Zwar kann ich mich leider nicht mehr daran erinnern wie dabei eine bestimmte BB gesucht wurde, doch ich weiss immerhin noch das es fix ging (oder ich hatte damals einfach irgendetwas falsch gemacht…)
Sei’s drum. Ich würde jetzt auch keine Hausdorff-Distanzen oder sowas berechnen wollen um die genaue BB mit dem NN drin zu finden. Aber vielleicht reicht der Ansatz ja um auf einfache Weise einige BBs von vornherein von der Suche auszuschließen. Das wäre ja schonmal ein Anfang.

@AmunRa :
Mensch klar… An die hatte ich ja gar nicht mehr gedacht, weil eigentlich bereits ausprobiert. Und zwar nur so, dass ich die Palette bei jedem Suchlauf neu “zentrierte” ud zwar auf die gesuchte Farbe. Jetzt wo du es gepostet hast, fällt es mir wie Schuppen aus den Haaren. Ich erstelle die BB oder eine BS ein mal und sortiere die Palette über die Distanz zum Center. Liegt die gewünschte Farbe ausserhalb dieser BS, suche ich von hinten nach vorn, andernfalls von vorne nach hinten. Denke mal schneller gehts nicht.

Edit: Habe das Swing-Beispiel mal angehängt, damit man weis, um was es geht.

Edit2: @Dow_Jones : Der Median-Cut ist ein wenig was anderes. Da wird zunächst eine Bounding-Box aus allen Farben erstellt und diese wird dann immer an ihren breitesten Stellen soweit unterteilt, bis die geforderte Anzahl an Farben erreicht ist oder sich die Boxen nicht mehr unterteilen lassen. Eine Beispiel-Implementation dazu findest du auch in der angehängten Anwendung.

@AmunRa : Mist. War zwar 'ne Tolle Idee, aber merklich schneller wirds dadurch auch nicht. Das ist von Bild zu Bild natürlich auch noch verschieden, aber irgendwie ist es egal, wonach man vorsortiert. Wenn man nach dem Abstand zu einem gemeinsamen Mittelpunkt sortiert, hat man recht häufig das Pech, dass die häufigsten Farben nicht an den Listenenden stehen, wodurch der Vorgang wieder genauso lange dauert, als wenn man nach Häufugkeit sortiert. Wenn man nach Häufigkeit sucht, spart man sich auch noch die Auswahl der Suchrichtung. Ich glaub, ich lass es so wie hier gepostet (glücklicherweise habe ich es gepostet).

wird mehrmals nach exakt denselben Wert gesucht?
hast du schon einen Cache überlegt, genau ablegen Suchfarbe X → naheste bekannte Referenzfarbe Y
(aber nein, du meinst hier wohl dass jede der 1000 Palettenfarbe je 480x gefunden wird)

ein Extrem wäre Vorabberechnung das gesamten Suchraums,
für alle möglichen Farben die Referenzfarbe ablegen,
Nachteil jede Menge (wenn nicht unmöglich viel) Platz und viel mehr Farben zu berechnen,
Vorteil alle auf einmal strukturiert, damit hoffentlich schneller als üblich zu machen

alles mit 3D-Raum, Abschnitte größer als int-genau müsste dazwischen liegen,
weitaus weniger Information gespeichert, durch Verzicht sicherlich auch schneller aufgebaut,
dafür Einzelsuche später dann doch nicht ein Schritt sondern ein paar Schritte

klingt etwas komisch in diese Richtung, ist nicht eher gemeint:
Suchfarbe hat Dimensionen 138, 75, 209 → Planraum 5, 3, 7 von 888 = 512 Planräumen zu je 32 Kantenlänge,
in diesem Raum liegen nur 50 von 1000 Farben, mit denen zu vergleichen ist
→ bis zu 95% Farbvergleiche gespart bei einfacher Bestimmung des Raumes?
(spätes edit: und noch bei den Nachbarn schauen für den Fall dass dort jemand näher ist, Flensburg die naheste Stadt für jemanden in Dänemark knapp an der Grenze, muss man alles richtig machen)


mit [quote=Spacerat;96267]wenn man nach Häufigkeit sortiert.[/quote] sprichst du auf direkten Treffer bei den ersten Farben an?
in solchen Situation steht es natürlich gut,
ist die Palette extra darauf angelegt, den häufigsten Farben genau zu entsprechen und gibt es häufige Farben die exakt treffen?
sobald auch nur ein wenig Abweichung musst du alle Farben durchgehen, oder?


welche Werte hat smallestError üblicherweise und wie setzt sich die Palette zusammen?
bei einem bereits gefundenen Abstand von nur 1 oder 0 je nach Rundung kannst du zwar noch weiter schauen nach exakten Treffer,
distance-Berechnung aber unnötig, kleiner als 1 oder 0 wird der Abstand wohl nicht mehr :wink:

mit dem aktuellen besten Abstand läßt sich die Distanzberechnung vielleicht auch optimieren,
erstmal simple Differenzberechnungen, wenn eine Koordinate bereits weiter entfernt als smallestError ist,
dann gleich Abbruch, nicht noch dick multiplizieren,

bei 100.000den Berechnungen mit bestimmen Palettenfarben und bis zu 1000 Rechnungen je Suchfarbe lohnt es sich vielleicht auch, die int-Werte vorher aufzuteilen, int der einzelnen Komponenten statt ständig >> zu rechnen?
edit: aber Zugriff auf Array oder besser (finale) Instanzvariable kann ja auch teuer sein…


wenn alle Palettenfarben mindesten je 10 voneinander entfernt sind, wäre bei einem Error von unter 5 abzubrechen, das könnte sparen,
aber auch wieder Arbeit womöglich, das von der Palette festzustellen, 1000 Farben untereinander kreuzen… :wink:

in dem Fall könnte es sich auch lohnen, von der vorherigen Suche aus weiter zu schauen, falls das der Pixel daneben im Bild war,
wenn Palettenfarben mindesten je 10 voneinander entfernt,
die vorherige Suchfarbe X Abstand 2 zu einer Palettenfarbe P hatte und nun Suchfarbe Y nur 2 von X entfernt ist, dann gehört zu Y auch P

Du kannst dir die hochgeladene Anwendung (Dithering.jar in Post #13) ja mal ansehen.

Bei den Reduzierungsalgorithmen wird zunächst ein Histogramm aller Farben gemacht, für Popularity-Cut in verschiedenen Reduzierungsstufen von 1 bis 8 Bit pro Farbe und für Median-Cut nur das volle 8-Bit-Spektrum. Beim Median-Cut werden dann die Farben zunächst alle in eine Box gepackt, welche dann an den jeweils breitesten Stellen unterteilt werden, bis entweder die für die Pixelbreite maximale Anzahl an Farben erreicht ist oder sich die Boxen nicht weiter teilen lassen (nur eine Farbe im Array verbleibt). Boxen in denen sich die meisten Farben versammeln, werden bei den Unterteilungen bevorzugt behandelt. Die entstandenen Paletten werden dann nach Häufigkeit sortiert und dadurch werden die am häufigsten verwendeten Farben am schnellsten gefunden. Natürlich wird bei Farbreduzierung stets davon ausgegangen, dass die gesuchte Farbe nicht 100%ig getroffen wird, das geht ja kaum, weil halt nicht mehr alle da sind.

AmunRa hatte jetzt den Vorschlag gemacht, dass man für die Farben die umgebende BoundingBox berechnet (ich hab’s gleich mit einer BoundingSpere versucht) und alle Farben der Länge nach zum Abstand des Mittelpunktes der BB sortiert. Je nachdem, am welchen Punkt (Zentrum oder Punkt auf umgebender Kugel) die gesuchte Farbe näher ist, kann man die Palette von Aussen oder Innen durchsuchen. Das machte den Suchvorgang aber leider nicht merklich schneller, weil die am häufigsten verwendeten Farben nun im ungünstigsten Fall genau zwischen dem Zentrum und der Aussenhülle liegen, was den eigentlich beschleunigten Suchvorgang wieder verlangsamt. Wenn man die Liste ständig nach dem Abstand zur gesuchten Farbe sortiert, ist man langsamer als zuvor. Feste Sortierungen nach Länge der Farbvektoren und einer beginnenden Suche bei der Länge der gesuchten Farbe hätte den Nachteil, dass eine Farbe, deren Länge zwar kürzer aber dennoch näher an der Gesuchten dran ist übersprungen würde.

Was die Aufteilung betrifft, da hatte ich schon R,G und B separat gespeichert, das machte auf meiner Kiste (8-Kerne mit 3,5GHz) aber keinen Unterschied, also hab ich’s gelassen. Selbiges galt auch für Float-Werte zwischen 0 und 1.

[quote=Spacerat]Mittelpunktes der BB[/quote] klingt nett auch wenn ich nicht allzu genau verstehe was ihr beide da plant
(oder nur du und @AmunRa eher bei meiner Idee :wink: ),
auch nicht zu genau zu verstehen versucht :wink: , lieber selber ein kleines Testprogramm, dauert auch so schon lange genug

ich habe deinen Code zum Vergleich zum Teil übernommen und eher noch vereinfacht (kein ==-Vergleich bei bei mir) statt zu optimieren,
ich teste hier auch mit völligen Zufallszahlen = Farben, keine Häufigkeiten-Sortierung usw., das muss dann zu deinem Programm keine Aussage haben

Idee: Palette von 1000 Farben, Aufspaltung des Raums in Würfel mit 16 Pixel Seitenlänge (Variable r),

für jeden der im Moment 161616 = 4092 Würfel von Mittelpunkt aus mit der ‚normalen Suche‘ durch alle Palettenfarben Kandidaten bestimmen,
die naheste Farbe sowie alle bis maximal Variable ‚radius‘ höheren Abstand,

diesen radius zu wählen ist für mich etwas kompliziert, problematisch bei dünn besetzten Paletten,
ferne Punkte haben hohe Differenzunterschiede nach der aktuellen Rechnung, da muss der radius eigentlich höher gewählt werden,
bei 1000 Farben wird es aber wohl nicht so viel Abstand geben, jedenfalls keine sichere Sache, alles provisorisch,

exakte normalisierte Abstandsberechnung wäre hilfreich, mit Tradeoff höhere Berechnungskosten, Wurzel…

im geposteten Beispiel sind 30-200 Farben in jedem der 4092 Würfel, ziemlich breit gefächert, aber leistet schon einiges,
bei der Suche wird wie schon mal vorgeschlagen zu jeder Suchfarbe erst der Würfel bestimmt, dann nur mit den Farben dort verglichen

Ergebnis akutell:
1000 Palette, 500.000 Zufallsfarben suchen,
Initialisierung: 0.2-0.3 sec
normale Suche mit Durchlauf über alle 1000 Palettenfarben: 3.3 sec
Suche mit Würfeln: 0.5 sec

Streichung des Faktors 5 beim Radius führt auch noch zur korrekten Checksumme, nur noch um die 20 Farben in jedem Würfel,
Suche mit Würfeln sinkt dann auf unter 0.1 sec bei mir

public class Test
{
    static Random rand = new Random(42);

    static final int nSearch = 500000;
    static Col[] search = new Col[nSearch];
    static int nPalette = 1000;
    static Col[] palette;

    static final int r = 16;
    static final int r2 = 256 / r;
    static final int radius = (int)(5 * 3 * r2 * 1.5 * r2 * 1.5);
    static final Col[][][][] room = new Col[r][r][r][];

    public static void main(String[] args)
    {
        debug("Start main");
        Set<Col> setP = new HashSet<Col>();
        do
        {
            setP.add(nextCol());
        }
        while (setP.size() < nPalette);
        palette = setP.toArray(new Col[nPalette]);
        Arrays.sort(palette); // Sortierung hier und in den Würfeln wichtig damit bei gleichen Abständen immer dieselbe Farbe gewählt wird

        for (int i = 0; i < r; i++)
            for (int j = 0; j < r; j++)
                for (int k = 0; k < r; k++)
                {
                    Set<Col> cand = new HashSet<Col>();
                    addCandidates((i + 0.5) * r2, (j + 0.5) * r2, (k + 0.5) * r2, cand, palette);
                    Col[] candA = cand.toArray(new Col[cand.size()]);
                    Arrays.sort(candA);
                    room**[j][k] = candA;
                }

        rand = new Random(44);
        for (int i = 0; i < nSearch; i++)
            search** = nextCol();

        searchAll();
        search3D();

    }

    static void searchAll()
    {
        debug("start All");
        long check = 0;
        for (Col cs : search)
        {
            check += nearestColor(cs, palette).hashCode();
        }
        debug("check: " + check);
    }

    static void search3D()
    {
        debug("start 3D");
        long check = 0;
        for (Col cs : search)
        {
            check += nearestColor(cs, room[cs.ri][cs.gi][cs.bi]).hashCode();
        }
        debug("check: " + check);
    }

    static void debug(String st)
    {
        System.out.println(System.currentTimeMillis() + " - " + st);
    }

    static Col nextCol()
    {
        return new Col(rand.nextInt(255), rand.nextInt(255), rand.nextInt(255));
    }

    static void addCandidates(double r, double g, double b, Set<Col> cand, Col[] pal)
    {

        Col mid = new Col((int)r, (int)g, (int)b);
        int smallestError = Integer.MAX_VALUE;
        int maxError = Integer.MAX_VALUE;
        for (Col color2 : pal)
        {
            int currentError = distanceSquared(mid, color2);
            if (smallestError > currentError)
            {
                smallestError = currentError;
                maxError = smallestError + radius;
            }
            if (currentError < maxError)
            {
                cand.add(color2);
            }
        }
        Iterator<Col> iter = cand.iterator(); // woher viele eingesammelt, nun wieder streichen was zuviel ist
        while (iter.hasNext())
        {
            Col next = iter.next();
            int currentError = distanceSquared(mid, next);
            if (currentError > maxError)
            {
                iter.remove();
            }
        }

    }

    static Col nearestColor(Col color1, Col[] pal)
    {
        int smallestError = Integer.MAX_VALUE;
        Col rc = null;
        for (Col color2 : pal)
        {
            int currentError = distanceSquared(color1, color2);
            if (smallestError > currentError)
            {
                smallestError = currentError;
                rc = color2;
            }
        }
        return rc;
    }

    static int distanceSquared(Col rgb1, Col rgb2)
    {
        int rd = rgb1.r - rgb2.r;
        int gd = rgb1.g - rgb2.g;
        int bd = rgb1.b - rgb2.b;
        return rd * rd + gd * gd + bd * bd;
    }

    static class Col
        implements Comparable<Col>
    {
        final int r;
        final int g;
        final int b;

        final int ri;
        final int gi;
        final int bi;

        final int hash;

        public Col(int r, int g, int b)
        {
            this.r = r;
            this.g = g;
            this.b = b;

            ri = r / r2;
            gi = g / r2;
            bi = b / r2;

            final int prime = 31;
            int result = 1;
            result = prime * result + b;
            result = prime * result + g;
            result = prime * result + r;
            hash = result;
        }

        /**
         * @inheritDoc
         */
        @Override
        public String toString()
        {
            return "Col [r=" + r + ", g=" + g + ", b=" + b + "] - [ri=" + ri + ", gi=" + gi + ", bi=" + bi + "]";
        }

        /**
         * @inheritDoc
         */
        @Override
        public int hashCode()
        {
            return hash;
        }

        /**
         * @inheritDoc
         */
        @Override
        public boolean equals(Object obj)
        {
            if (this == obj) return true;
            if (obj == null) return false;
            if (getClass() != obj.getClass()) return false;
            Col other = (Col)obj;
            if (b != other.b) return false;
            if (g != other.g) return false;
            if (r != other.r) return false;
            return true;
        }

        /**
         * @inheritDoc
         */
        public int compareTo(Col o)
        {
            int c = r - o.r;
            if (c != 0) return c;
            c = g - o.g;
            if (c != 0) return c;
            return b - o.b;
        }

    }
}

Dein Beispiel entspräche bei mir der Farbauflösung von 12 Bit (etwas drüber, ich hab da nur 161615, damit ich Reserve für eine Transparenzfarbe habe). Und die Suche, die AmunRa vorgeschlagen hat, entspricht auch genau deiner (Mittelpunkt der BoundingBox), nur halt mit nur einer BB. Du verwendest, soweit ich das überblicke 4096 (was bei 12 Bit und drunter natürlich sofort zu einem Ergebnis führt). Das werde ich mir noch mal genauer ansehen, sieht zumindest schon mal schneller aus.
Bei Random-Tests ist das Histogramm der Original-Farben im Übrigen gar nicht notwendig, weil damit nur die reduzierten Farben der Palette bestimmt werden. Wichtig ist nur die Vorpreparation dieser Tabelle, damit man halt nur in Frage kommende Teile davon durchsuchen muss.

entscheidend ist die Frage was du bei deinem ursprünglichen Code mit

        color2 = (int) palette.readColor(n);

real vorliegen hast:
wenn in 90% der Fälle bei den ersten 10 Paletten-Farben schon Treffer und Abbruch kommen, dann vielleicht schnell genug,

wenn du aber relativ oft ALLE Farben durchgehst, bei 500.000 Suchen 50 bis gar Maximum 500 Mio. Vergleiche hast,
dann sollte auf jeden Fall eine Optimierung um 95%+ möglich sein, das geht ja gar nicht

falls es so einfach mit den 3 Dimensionen usw. geht,
‘Farbauflösung von 12 Bit’ usw. klingt wiederum etwas danach, dass ich vielleicht noch nicht alles erfasst habe

Bisher kommt bei “readColor(n)” die Farbe aus einer nach Häufigkeit sortierten Farbliste.

Evtl. hast du ja den Sinn von Farbreduzierung nicht verstanden: Es geht darum, DirectColor-Modelle zu indizieren, das heisst, sich aus bei 24 Bit Farben die 2, 4, 8… 65536 am besten geeigneten Farben herauszufiltern, die das Bild möglichst gut darstellen. Die 12 Bit entsprächen dabei 4096 24-Bit breite Farben. Bei einem Bit hast du 2 (Schwarz-Weis) und bei 16-Bit halt 65536 Farben. Welche Farben am besten geeignet sind kann man über drei Arten bestimmen:

  1. Uniform Subdivisions: Alle Farben werden gleichmässig “beschnitten”, das heisst, es wird keine Suche in einer Palette fällig, sondern ein Berechnungsalgorithmus. Diese Art der Farbauswahl ist die schnellste.
  2. Popularity-Cut: Es wird eine Palette der lt. Histogramm am häufigsten verwendeten Farben erstellt, die restlichen Farben werden eliminiert.
  3. Median-Cut: Alle Farben des Histogramms werden in einen Farbwürfel gesammelt, wobei maximale R-, G- und B-Ausdehnungen festgestellt und Häufigkeiten zusammengezählt werden. Dieser Würfel wird dann so oft unterteilt, bis die reduzierte Palette voll ist oder sich die Würfel (bzw. inzwischen Quader) nicht mehr unterteilen lassen. Unterteilt werden jeweils die Quader mit den Farben, die zusammen am häufigsten verwendet werden. Gegenüber dem Popularity-Cut, hat diese Methode den Vorteil, dass mehr von den sonst eliminierten Farbtönen in solchen Quadern erhalten bleiben.

Nachdem für 2. und 3. die Paletten erstellt wurden, sind diese nach den am häufigsten auftretenden Farben sortiert. Das macht aber halt bei der Suche nach der passenden reduzierten Farbe genau dann Probleme, wenn mehrere Farbtöne gleichmässig oft verwendet wurden. Da möchte man spätestens bei dem 4. am häufigsten verwendeten Ton am liebsten schon in der Mitte anfangen zu suchen.

Edit: Verdammt! In mehreren Würfeln suchen bringt es anscheinend auch nicht, weil viel zu viele davon gar nicht definiert werden, also null bleiben. Die Farbe müsste in diesem Fall wieder in einem anderen Würfel gesucht werden, nur in welchem. Frage ist also, wie fülle ich die Lücken der Suchwürfel. Welche Farben sollten dahin? Ich habe irgendwie das Gefühl als sei da jetzt was doppelt gemoppelt, zumal ich ja schon diese Quader beim Median-Cut erstelle. Ich müsste selbiges ja nun auch für den Popularity-Cut anwenden. Naja… ich überleg nochmal ein wenig. Da muss doch was zu schaffen sein.