algorithm - Follow-up: "Sortieren" von Farben nach Unterscheidungskraft

Translate

Ursprüngliche Frage

Wenn Sie N maximal entfernte Farben (und eine zugehörige Abstandsmetrik) erhalten, können Sie dann eine Möglichkeit finden, diese Farben in einer bestimmten Reihenfolge zu sortieren, sodass die ersten M auch einer maximal unterschiedlichen Menge ziemlich nahe kommen?

Mit anderen Worten, angesichts einer Reihe unterschiedlicher Farben muss eine Bestellung erstellt werden, damit ich von Anfang an so viele Farben verwenden kann, wie ich benötige, und ich kann mir sicher sein, dass sie alle unterschiedlich sind und dass auch Farben in der Nähe sehr unterschiedlich sind (z. bläuliches Rot steht nicht neben rötlichem Blau).

Randomisierung ist in Ordnung, aber sicherlich nicht optimal.

Erläuterung: Bei einigen großen und visuell unterschiedlichen Farben (z. B. 256 oder 1024) möchte ich sie so sortieren, dass ich bei Verwendung der ersten, z. B. 16, eine relativ visuell unterschiedliche Teilmenge von Farben erhalte. Dies entspricht in etwa der Aussage, dass ich diese Liste von 1024 so sortieren möchte, dass sie umso weiter voneinander entfernt sind, je näher die einzelnen Farben visuell sind.

This question and all comments follow the "Attribution Required."

Alle Antworten

Translate

Das klingt für mich auch nach einer ArtWiderstandsgraphwo Sie versuchen, den Weg des geringsten Widerstands zu bestimmen. Wenn Sie die Anforderungen, den Pfad des maximalen Widerstands, umkehren, kann dies möglicherweise verwendet werden, um einen Satz zu erstellen, der von Anfang an eine maximale Differenz erzeugt und gegen Ende zu Werten zurückkehrt, die näher an den anderen liegen.

Hier ist zum Beispiel eine Möglichkeit, vielleicht das zu tun, was Sie wollen.

  1. Berechnen Sie die Entfernung (Refdein anderer Beitrag) von jeder Farbe zu allen anderen Farben
  2. Summieren Sie die Abstände für jede Farbe, dies gibt Ihnen einen Hinweis fürWie weit ist diese Farbe von allen anderen Farben insgesamt entfernt?
  3. Ordne die Liste nach Entfernung und gehe nach unten

Dies würde anscheinend eine Liste erzeugen, die mit der Farbe beginnt, die am weitesten von allen anderen Farben entfernt ist, und dann nach unten geht. Die Farben gegen Ende der Liste wären im Allgemeinen näher an anderen Farben.

Bearbeiten: Das Lesen Ihrer Antwort auf meinen ersten Beitrag über die räumliche Unterteilung würde nicht genau zur obigen Beschreibung passen, da Farben, die anderen Farben nahe kommen, am Ende der Liste stehen würden, aber nehmen wir an, Sie haben irgendwo eine Farbgruppe Mindestens eine der Farben aus diesem Cluster würde sich am Anfang der Liste befinden, und es wäre diejenige, die im Allgemeinen am weitesten von allen anderen Farben insgesamt entfernt ist. Wenn das Sinn macht.

Quelle
Translate

Dieses Problem wird als Farbquantisierung bezeichnet und weist viele bekannte Algorithmen auf:http://en.wikipedia.org/wiki/Color_quantizationIch kenne Leute, die den Octree-Ansatz effektiv umgesetzt haben.

Quelle
Translate

Es scheint, dass Ihnen die Wahrnehmung wichtig ist. In diesem Fall möchten Sie möglicherweise mit einem wahrnehmbaren Farbraum wie YUV, YCbCr oder Lab arbeiten. Jedes Mal, wenn ich diese verwendet habe, haben sie mir viel bessere Ergebnisse gebracht als sRGB allein.

Das Konvertieren von und zu sRGB kann schmerzhaft sein, aber in Ihrem Fall könnte es den Algorithmus tatsächlich vereinfachen und als Bonus funktioniert es meistens auch für Farbenjalousien!

Quelle
Translate

N maximal entfernte Farben können als eine Menge gut verteilter Punkte in einem dreidimensionalen (Farb-) Raum betrachtet werden. Wenn Sie sie aus einem generieren könnenHalton-SequenzDann besteht jedes Präfix (die ersten M Farben) auch aus gut verteilten Punkten.

Quelle
Translate

Wenn ich die Frage richtig verstehe, möchten Sie die Teilmenge von erhaltenMFarben mit demhöchste mittlere Entfernungzwischen Farben, gegeben einige Distanzfunktiond.

Anders ausgedrückt, unter Berücksichtigung des ursprünglichen Satzes vonNFarben als großes, ungerichtetes Diagramm, in dem alle Farben verbunden sind, möchten Sie die findenlängster Wegdas besucht keineMKnoten.

Ich fürchte, das Lösen von NP-vollständigen Graphproblemen ist mir ein Rätsel, aber Sie könnten versuchen, eine einfache physikalische Simulation durchzuführen:

  1. GenerierenMzufällige Punkte im Farbraum
  2. Berechnen Sie den Abstand zwischen den einzelnen Punkten
  3. Berechnen Sie Abstoßungsvektoren für jeden Punkt, der ihn von allen anderen Punkten entfernt (mit 1 / ())Entfernung^ 2) als Größe des Vektors)
  4. Summiere die Abstoßungsvektoren für jeden Punkt
  5. Aktualisieren Sie die Position jedes Punkts gemäß den summierten Abstoßungsvektoren
  6. Beschränken Sie nicht gebundene Koordinaten (z. B. wenn die Leuchtkraft negativ wird oder über einer liegt).
  7. Wiederholen Sie ab Schritt 2, bis sich die Punkte stabilisiert haben
  8. Wählen Sie für jeden Punkt die nächstgelegene Farbe aus dem ursprünglichen Satz ausN

Es ist alles andere als effizient, aber für kleineMEs kann effizient genug sein und nahezu optimale Ergebnisse liefern.

Wenn Ihre Farbabstandsfunktion einfach ist, gibt es möglicherweise eine deterministischere Methode zum Generieren der optimalen Teilmenge.

Quelle
Translate
  1. Beginnen Sie mit zwei Listen. CandidateColors, das anfänglich Ihre unterschiedlichen Farben enthält, und SortedColors, das anfänglich leer ist.
  2. Wählen Sie eine Farbe aus, entfernen Sie sie aus CandidateColors und fügen Sie sie in SortedColors ein. Dies ist die erste Farbe und wird die häufigste sein. Daher ist es ein guter Ort, um eine Farbe auszuwählen, die gut zu Ihrer Anwendung passt.
  3. Berechnen Sie für jede Farbe in CandidateColors den Gesamtabstand. Die Gesamtentfernung ist die Summe der Entfernung zwischen CandidateColor und jeder Farbe in SortedColors.
  4. Entfernen Sie die Farbe mit dem größten Gesamtabstand von CandidateColors und fügen Sie sie am Ende von SortedColors hinzu.
  5. Wenn CandidateColors nicht leer ist, fahren Sie mit Schritt 3 fort.

Dieser gierige Algorithmus sollte Ihnen gute Ergebnisse liefern.

Quelle
Translate

Sie können die Kandidatenfarben einfach nach dem maximalen Abstand des minimalen Abstands zu einer der Indexfarben sortieren.

Verwendung des euklidischen Farbabstands:

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);
}

Sie können es jedoch durch alles ersetzen, was Sie möchten. Es braucht nur eine Farbabstandsroutine.

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;
            }
        }
    }
}
Quelle
Translate

Meinen Sie damit, dass Sie aus einer Menge von N Farben M Farben auswählen müssen, wobei M <N ist, so dass M die istBesteDarstellung der N Farben im M Raum?

Reduzieren Sie als besseres Beispiel einen Echtfarbraum (24-Bit-Farbraum) auf einen 8-Bit-Farbraum (GIF?).

Hierfür gibt es Quantisierungsalgorithmen wie dieAdaptive räumliche Unterteilungvon ImageMagic verwendeter Algorithmus.

Diese Algorithmen wählen normalerweise nicht nur vorhandene Farben aus dem Quellraum aus, sondern erstellen im Zielraum neue Farben, die den Quellfarben am ähnlichsten sind. Als vereinfachtes Beispiel: Wenn Sie im Originalbild drei Farben haben, von denen zwei rot sind (mit unterschiedlicher Intensität oder Blautönen usw.) und die dritte blau ist und auf zwei Farben reduziert werden muss, kann das Zielbild eine rote Farbe haben Das ist eine Art Durchschnitt der ursprünglichen zwei roten + blauen Farben aus dem Originalbild.

Wenn du noch etwas brauchst, habe ich deine Frage nicht verstanden :)

Quelle
Translate

Sie können sie in das RGB-HEX-Format aufteilen, um das R mit Rs einer anderen Farbe zu vergleichen, die mit G und B identisch sind.

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

Sie müssen also nur entscheiden, wie nah die Farben sein sollen und was ein akzeptabler Unterschied für die Segmente ist, die als unterschiedlich angesehen werden.

Quelle