Suivi:« Tri » des couleurs par caractère distinctif

Question

Question originale

Si on vous donne N couleurs maximalement distantes (et une métrique de distance associée), pouvez-vous trouver un moyen de trier ces couleurs dans un ordre tel que les premiers M soient également raisonnablement proches d'être un ensemble maximalment distinct ?

En d'autres termes, étant donné un ensemble de couleurs distinctes, établissez un ordre afin que je puisse utiliser autant de couleurs que nécessaire dès le début et être raisonnablement assuré qu'elles sont toutes distinctes et que les couleurs proches sont également très distinctes (par exemple, le rouge bleuâtre n'est pas à côté du bleu rougeâtre).

La randomisation est acceptable mais certainement pas optimale.

Clarification:Étant donné un ensemble de couleurs vaste et visuellement distinct (disons 256 ou 1024), je souhaite les trier de telle sorte que lorsque j'utilise les premiers, disons, 16 d'entre elles, j'obtienne un sous-ensemble de couleurs relativement visuellement distinct.Cela équivaut, en gros, à dire que je veux trier cette liste de 1024 de sorte que plus les couleurs individuelles sont visuellement proches, plus elles sont éloignées sur la liste.

Answer 1

Cela me semble aussi être une sorte de graphique de résistance où vous essayez de tracer le chemin de moindre résistance.Si vous inversez les exigences, chemin de résistance maximale, cela pourrait peut-être être utilisé pour produire un ensemble qui dès le début produit une différence maximale au fur et à mesure, et vers la fin commence à revenir à des valeurs plus proches des autres.

Par exemple, voici une façon de faire ce que vous voulez.

1. Calculer la distance (réf ton autre message) de chaque couleur à toutes les autres couleurs
2. Additionnez les distances pour chaque couleur, cela vous donne une indication pour à quelle distance se trouve cette couleur de toutes les autres couleurs au total
3. Classez la liste par distance, en descendant

Cela semblerait produire une liste qui commence par la couleur la plus éloignée de toutes les autres couleurs, puis descendrait, les couleurs vers la fin de la liste seraient plus proches des autres couleurs en général.

Modifier:La lecture de votre réponse à mon premier message, sur la subdivision spatiale, ne correspondrait pas exactement à la description ci-dessus, puisque les couleurs proches des autres couleurs tomberaient en bas de la liste, mais disons que vous avez un groupe de couleurs quelque part, au moins une des couleurs de ce groupe seraient situées près du début de la liste, et ce serait celle qui serait généralement la plus éloignée de toutes les autres couleurs au total.Si ça a du sens.

Answer 2

Ce problème est appelé quantification des couleurs et comporte de nombreux algorithmes bien connus : http://en.wikipedia.org/wiki/Color_quantization Je connais des gens qui ont mis en œuvre l'approche octree avec succès.

Answer 3

Il semble que la perception soit importante pour vous, dans ce cas, vous voudrez peut-être envisager de travailler avec un espace colorimétrique perceptuel tel que YUV, YCbCr ou Lab.Chaque fois que je les ai utilisés, ils m'ont donné de bien meilleurs résultats que le sRGB seul.

La conversion vers et depuis sRGB peut être pénible, mais dans votre cas, cela pourrait en fait simplifier l'algorithme et, en prime, il fonctionnera également principalement pour les daltoniens !

Answer 4

N couleurs les plus éloignées peuvent être considérées comme un ensemble de points bien répartis dans un espace (colorique) tridimensionnel.Si vous pouvez les générer à partir d'un Séquence Halton, alors tout préfixe (les M premières couleurs) est également constitué de points bien répartis.

Answer 5

Si je comprends bien la question, vous souhaitez obtenir le sous-ensemble de M couleurs avec le distance moyenne la plus élevée entre les couleurs, étant donné une certaine fonction de distance d.

Autrement dit, en considérant l’ensemble initial de N couleurs sous la forme d'un grand graphique non orienté dans lequel toutes les couleurs sont connectées, vous souhaitez trouver la le chemin le plus long qui visite n'importe qui M nœuds.

Résoudre les problèmes de graphes NP-complets me dépasse bien, j'en ai peur, mais vous pouvez essayer d'exécuter une simple simulation physique :

1. Générer M points aléatoires dans l'espace colorimétrique
2. Calculer la distance entre chaque point
3. Calculez les vecteurs de répulsion pour chaque point qui l'éloigneront de tous les autres points (en utilisant 1 / (distance ^ 2) comme la grandeur du vecteur)
4. Additionner les vecteurs de répulsion pour chaque point
5. Mettre à jour la position de chaque point en fonction des vecteurs de répulsion additionnés
6. Contraindre toutes les coordonnées hors limites (telles que la luminosité devenant négative ou supérieure à un)
7. Répétez à partir de l'étape 2 jusqu'à ce que les points se stabilisent
8. Pour chaque point, sélectionnez la couleur la plus proche dans l'ensemble original de N

C'est loin d'être efficace, mais pour les petits M cela peut être suffisamment efficace et donnera des résultats presque optimaux.

Si votre fonction de distance de couleur est simple, il peut exister une manière plus déterministe de générer le sous-ensemble optimal.

Answer 6

1. Commencez avec deux listes.CandidateColors, qui contient initialement vos couleurs distinctes et SortedColors, qui est initialement vide.
2. Choisissez n'importe quelle couleur, supprimez-la de CandidateColors et placez-la dans SortedColors.Il s'agit de la première couleur et sera la plus courante, c'est donc un bon endroit pour choisir une couleur qui correspond bien à votre application.
3. Pour chaque couleur dans CandidateColors, calculez sa distance totale.La distance totale est la somme de la distance entre CandidateColor et chacune des couleurs de SortedColors.
4. Supprimez la couleur avec la plus grande distance totale de CandidateColors et ajoutez-la à la fin de SortedColors.
5. Si CandidateColors n’est pas vide, revenez à l’étape 3.

Cet algorithme gourmand devrait vous donner de bons résultats.

Answer 7

Vous pouvez simplement trier les couleurs candidates en fonction de la distance maximale de la distance minimale par rapport à l'une des couleurs d'index.

Utilisation de la distance de couleur euclidienne :

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

Bien que vous puissiez le remplacer par tout ce que vous voulez.Il suffit d’une routine de distance de couleur.

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

Answer 8

Voulez-vous dire que parmi un ensemble de N couleurs, vous devez choisir M couleurs, où M < N, de telle sorte que M soit le meilleur représentation des N couleurs dans l'espace M ?

À titre d'exemple, réduisez une couleur vraie (espace colorimétrique 24 bits) à un espace colorimétrique mappé 8 bits (GIF ?).

Il existe des algorithmes de quantification pour cela, comme le Subdivision spatiale adaptative algorithme utilisé par ImageMagic.

Ces algorithmes ne se contentent généralement pas de sélectionner les couleurs existantes dans l'espace source, mais créent de nouvelles couleurs dans l'espace cible qui ressemblent le plus aux couleurs source.À titre d'exemple simplifié, si vous avez 3 couleurs dans l'image d'origine dont deux sont rouges (avec des intensités différentes ou des teintes bleutées, etc.) et la troisième est bleue, et que vous devez réduire à deux couleurs, l'image cible pourrait avoir une couleur rouge. c'est une sorte de moyenne des deux couleurs originales rouges + la couleur bleue de l'image originale.

Si vous avez besoin d'autre chose, je n'ai pas compris votre question :)

Answer 9

Vous pouvez les diviser au format RVB HEX afin de pouvoir comparer le R avec des R d'une couleur différente, de même avec le G et le B.

Même format que 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

Ainsi, la seule chose que vous devez décider est de savoir à quel point vous souhaitez que les couleurs soient proches et quelle est la différence acceptable pour que les segments soient considérés comme différents.