Followup: „Sortieren“ Farben durch Unverwechselbarkeit

stimmen
18

Original Question

Wenn Sie N maximal entfernten Farben (und einige zugehörigen Abstandsmetrik) gegeben sind, können Sie mit einer Art und Weise kommen die Farben in einer bestimmten Reihenfolge, so dass die erste M auch zum Sein ein maximal unterscheidbaren Satz einigermaßen nahe zu sortieren?

Mit anderen Worten, ein Bündel von verschiedenen Farben gegeben, mit einer Bestellung kommen, damit ich so viele Farben verwenden kann, wie ich am Anfang müssen beginnen und einigermaßen sicher sein, dass sie alle verschieden sind und dass in der Nähe Farben sind auch sehr verschieden (zB blaurot ist nicht neben blau bis rötlich).

Randomisierung ist in Ordnung, aber sicherlich nicht optimal.

Zur Verdeutlichung: Bei einigen großen und visuell unterscheidbaren Satz von Farben (etwa 256 oder 1024), ich möchte, dass sie so sortieren, dass wenn ich den ersten, sagen wir, 16 von ihnen, dass ich eine relativ visuell unterschiedliche Teilmenge von Farben. Dies entspricht in etwa, zu sagen, dass ich diese Liste von 1024 sortiert werden soll, so dass die näheren einzelne Farben visuell sind, desto weiter auseinander sie auf der Liste steht.

Veröffentlicht am 04/08/2008 um 16:14
quelle vom benutzer
In anderen Sprachen...                            


9 antworten

stimmen
2

N maximal entfernte Farben können eine Reihe von gut verteilten Punkten in einem 3-dimensionalen (Farbe) Raum betrachtet werden. Wenn man sie aus einen generieren kann Halton - Folge , dann ist jeder Präfix (die erste M Farben) besteht ebenfalls aus gut verteilten Punkten.

Beantwortet am 25/08/2008 um 09:44
quelle vom benutzer

stimmen
2

Es scheint Wahrnehmung für Sie wichtig ist, in diesem Fall, dass Sie vielleicht mit einem wahrnehmbaren Farbraum betrachten wollen arbeiten wie YUV, YCbCr oder Lab. Jedesmal, wenn ich diejenigen verwendet habe, haben sie mir viel bessere Ergebnisse als sRGB allein.

Konvertierung in und aus sRGB kann ein Schmerz, aber in Ihrem Fall könnte es tatsächlich den Algorithmus einfacher und als Bonus macht es vor allem für Farbe Jalousien arbeiten!

Beantwortet am 12/08/2008 um 13:33
quelle vom benutzer

stimmen
2

Dieses Problem wird Farbquantisierung genannt, und hat viele bekannte Algorithmen: http://en.wikipedia.org/wiki/Color_quantization Ich kenne Leute, die Octree Ansatz für eine gute Wirkung umgesetzt.

Beantwortet am 12/08/2008 um 13:11
quelle vom benutzer

stimmen
2

Das klingt auch für mich wie eine Art von Widerstand Graphen , wo Sie versuchen , den Weg des geringsten Widerstands zu kartieren. Wenn Sie die Anforderungen, Weg der maximalen Widerstand invers, ist es vielleicht verwendet werden könnte , um einen Satz zu erzeugen , dass von Anfang an erzeugt maximale Differenz , wie Sie gehen, und gegen Ende beginnt auf Werte zurückgehen näher an die anderen.

Zum Beispiel, hier ist ein Weg, um vielleicht das tun, was Sie wollen.

  1. Berechnen Sie den Abstand (ref Ihre andere Post ) von jeder Farbe zu allen anderen Farben
  2. Addieren Sie die Abstände für jede Farbe, das gibt Ihnen einen Hinweis für , wie weit entfernt diese Farbe von allen anderen Farben insgesamt ist
  3. Bestellen Sie die Liste nach Entfernung, going down

Dies würde, so scheint es, produziert eine Liste, die mit der Farbe beginnt, die von allen anderen Farben am weitesten entfernt ist, und dann nach unten gehen, Farben gegen Ende der Liste würden im Allgemeinen zu anderen Farben näher sein.

Edit: Lesen Ihrer Antwort auf mein erster Beitrag, über die räumliche Unterteilung würde nicht genau passen die obige Beschreibung, da Farben in der Nähe zu anderen Farben an der Unterseite der Liste fallen würde, aber lassen Sie uns sagen, Sie haben eine Gruppe von Farben irgendwo auf mindestens eine der Farben aus diesem Cluster würde nahe dem Anfang der Liste befindet, und es würde die sein, die von allen anderen Farben insgesamt war am weitesten entfernt im allgemeinen. Wenn das Sinn macht.

Beantwortet am 04/08/2008 um 16:38
quelle vom benutzer

stimmen
1

Sie könnten nur die Kandidaten Farben auf dem Maximal distanzierte der Mindestabstand zu einem der Indexfarben basierend sortieren.

Mit euklidischem Farbabstand:

public double colordistance(Color color0, Color color1) {
    int c0 = color0.getRGB();
    int c1 = color1.getRGB();
    return distance(((c0>>16)&0xFF), ((c0>>8)&0xFF), (c0&0xFF), ((c1>>16)&0xFF), ((c1>>8)&0xFF), (c1&0xFF));
}

public double distance(int r1, int g1, int b1, int r2, int g2, int b2) {
    int dr = (r1 - r2);
    int dg = (g1 - g2);
    int db = (b1 - b2);
    return Math.sqrt(dr * dr + dg * dg + db * db);
}

Auch wenn Sie es mit etwas ersetzen können Sie wollen. Es braucht nur einen Farbabstand Routine.

public void colordistancesort(Color[] candidateColors, Color[] indexColors) {
    double current;

    double distance[] = new double[candidateColors.length];
    for (int j = 0; j < candidateColors.length; j++) {
        distance[j] = -1;
        for (int k = 0; k < indexColors.length; k++) {
            current = colordistance(indexColors[k], candidateColors[j]);
            if ((distance[j] == -1) || (current < distance[j])) {
                distance[j] = current;
            }
        }
    }

    //just sorts.
    for (int j = 0; j < candidateColors.length; j++) {
        for (int k = j + 1; k < candidateColors.length; k++) {
            if (distance[j] > distance[k]) {
                double d = distance[k];
                distance[k] = distance[j];
                distance[j] = d;

                Color m = candidateColors[k];
                candidateColors[k] = candidateColors[j];
                candidateColors[j] = m;
            }
        }
    }
}
Beantwortet am 03/09/2012 um 21:50
quelle vom benutzer

stimmen
1
  1. Beginnen Sie mit zwei Listen. CandidateColors, die zunächst Ihre unterschiedlichen Farben und SortedColors enthält, die zunächst leer.
  2. Wählen Sie jede mögliche Farbe und entfernen Sie sie aus CandidateColors und steckte es in SortedColors. Dies ist die erste Farbe und die häufigste sein, so ist es ein guter Ort, um eine Farbe zu wählen, die gut mit Ihrer Anwendung jives.
  3. Für jede Farbe in CandidateColors berechnet seine Gesamtdistanz. Der Gesamtabstand ist die Summe aus dem Abstand von der CandidateColor zu jedem der Farben in SortedColors.
  4. Entfernen Sie die Farbe mit der größten Gesamtdistanz von CandidateColors und fügen Sie es bis zum Ende des SortedColors.
  5. Wenn CandidateColors nicht leer ist, gehen Sie zurück zu Schritt 3.

Dieser Greedy-Algorithmus sollten Sie gute Ergebnisse.

Beantwortet am 21/11/2008 um 10:29
quelle vom benutzer

stimmen
1

Wenn ich die Frage richtig bin zu verstehen, wollen Sie die Teilmenge von erhalten , M Farben mit dem höchsten mittleren Abstand zwischen den Farben, in einiger Entfernung Funktion gegeben d .

Anders ausgedrückt, die erste Reihe von Berücksichtigung N Farben als ein großen, ungerichteten Graphen , in dem alle Farben verbunden sind, möchten Sie die finden längsten Weg , die alle besuchen M - Knoten.

NP-vollständige Graph Probleme zu lösen, ist weit über mir, ich habe Angst, aber Sie könnten versuchen, eine einfache physikalische Simulation ausgeführt wird:

  1. Generieren M zufällige Punkte im Farbraum
  2. Berechnen des Abstandes zwischen jedem Punkt
  3. Berechnen Abstoßungsvektoren für jeden Punkt , dass es weg von allen anderen Punkten bewegen wird (unter Verwendung von 1 / ( Abstand ^ 2) , wenn die Größe des Vektors)
  4. Zusammengefasst die Abstoßungsvektoren für jeden Punkt
  5. Aktualisieren, um die Position eines jeden Punktes gemäß den summierten Vektoren Abstoßungs
  6. Constrain jede aus gebundenen Koordinaten (wie Helligkeit oder negativ gehen über einen)
  7. Wiederholen von Schritt 2, bis die Punkte zu stabilisieren
  8. Für jeden Punkt, wählen Sie die nächste Farbe aus dem ursprünglichen Satz von N

Es ist weit von effizienten, aber für kleine M kann es effizient genug sein, und es wird eine nahezu optimale Ergebnisse.

Wenn Ihre Funktion Farbabstand einfach ist, kann es eine deterministische Art und Weise sein, die optimale Teilmenge zu erzeugen.

Beantwortet am 16/10/2008 um 18:11
quelle vom benutzer

stimmen
0

Sie können sie in RGB-HEX-Format aufgeteilt, so dass Sie die R mit R einer anderen Farbe zu vergleichen, das gleiche mit der G und B.

Gleiches Format wie HTML

XX XX XX
RR GG BB

00 00 00 = black
ff ff ff = white
ff 00 00 = red
00 ff 00 = green
00 00 ff = blue

Das einzige, was würden Sie brauchen, um zu entscheiden ist, wie nah Sie die Farben wollen und was ein akzeptabler Unterschied für die Segmente zu verschiedenen in Betracht gezogen werden.

Beantwortet am 04/08/2008 um 16:31
quelle vom benutzer

stimmen
0

Haben Sie bedeuten , dass aus einer Menge von N Farben, müssen Sie M Farben auswählen, wobei M <N, so dass M das ist beste Darstellung der N Farben in der M Raum?

Als ein besseres Beispiel eine True-Color (24 Bit Farbraum) auf einen 8-Bit-abgebildeten Farbraum (GIF?) Reduzieren.

Es gibt Quantisierung Algorithmen für diese, wie der Adaptive Spatial Vorort - Algorithmus von ImageMagick verwendet.

Diese Algorithmen in der Regel nicht nur wählen vorhandenen Farben aus dem Quellraum, sondern schafft neue Farben in dem Zielraum, die am ehesten die Quell Farben ähneln. Als vereinfachtes Beispiel, wenn Sie haben 3 Farben im Originalbild, in der zwei rot (mit unterschiedlicher Intensität oder bläuliche Farbtöne etc.) und die dritte ist blau, und müssen zwei Farben reduzieren, könnte das Zielbild eine rote Farbe haben das ist eine Art Durchschnitt der ursprünglichen zwei roten + die blauen Farbe aus dem Originalbild.

Wenn Sie etwas anderes brauchen, dann habe ich nicht verstehe Ihre Frage :)

Beantwortet am 04/08/2008 um 16:29
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more