algorithm - Seguimiento: "Clasificación" de colores por carácter distintivo

language-agnostic colors

Question

Pregunta original

Si le dan N colores máximos distantes (y alguna medida de distancia asociada), ¿puede encontrar una manera de ordenar esos colores en un orden tal que los primeros M también estén razonablemente cerca de ser un conjunto máximo distinto?

En otras palabras, dado un montón de colores distintos, propongo un orden para poder usar todos los colores que necesito comenzando desde el principio y estar razonablemente seguro de que son todos distintos y que los colores cercanos también son muy distintos (por ejemplo, el rojo azulado no está junto al azul rojizo).

La aleatorización está bien pero ciertamente no es óptima.

Aclaración: dado un conjunto de colores grande y visualmente distinto (digamos 256, o 1024), quiero ordenarlos de manera que cuando uso el primero, digamos 16 de ellos, obtengo un subconjunto de colores relativamente visualmente distinto. Esto es equivalente, más o menos, a decir que quiero ordenar esta lista de 1024 para que los colores individuales más cercanos sean visualmente, cuanto más separados estén en la lista.

Answer 1

Este problema se llama cuantificación del color y tiene muchos algoritmos conocidos: http://en.wikipedia.org/wiki/Color_quantization Conozco a las personas que implementaron el enfoque de octree con buenos resultados.

Answer 2

¿Quiere decir que a partir de un conjunto de N colores, debe elegir M colores, donde M <N, tal que M es la mejor representación de los N colores en el espacio M?

Como un mejor ejemplo, reduzca un color verdadero (espacio de color de 24 bits) a un espacio de color mapeado de 8 bits (GIF?).

Existen algoritmos de cuantificación para esto, como el algoritmo de subdivisión espacial adaptable utilizado por ImageMagic.

Estos algoritmos generalmente no solo seleccionan colores existentes del espacio de origen, sino que crean nuevos colores en el espacio objetivo que se asemejan más a los colores de origen. Como un ejemplo simplificado, si tiene 3 colores en la imagen original donde dos son rojos (con diferente intensidad o tintes azulados, etc.) y el tercero es azul, y necesita reducir a dos colores, la imagen objetivo podría tener un color rojo eso es algún tipo de promedio de los dos originales rojos + el color azul de la imagen original.

Si necesitas algo más, entonces no entendí tu pregunta :)

Answer 3

Puede dividirlos en formato RGB HEX para que pueda comparar la R con las R de un color diferente, lo mismo con G y B.

El mismo formato 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

Entonces, lo único que tendría que decidir es qué tan cerca quiere los colores y cuál es una diferencia aceptable para que los segmentos se consideren diferentes.

Answer 4

Parece que la percepción es importante para usted; en ese caso, es posible que desee considerar trabajar con un espacio de color perceptivo como YUV, YCbCr o Lab. Cada vez que los uso, me han dado mejores resultados que sRGB solo.

Convertir desde y hacia sRGB puede ser una molestia, pero en su caso podría hacer que el algoritmo sea más simple y, como beneficio adicional, ¡también funcionará para daltónicos!

Answer 5

N colores más distantes se pueden considerar como un conjunto de puntos bien distribuidos en un espacio tridimensional (color). Si puede generarlos a partir de una secuencia Halton , entonces cualquier prefijo (los primeros colores M) también consta de puntos bien distribuidos.

Answer 6

Si estoy entendiendo la pregunta correctamente, desea obtener el subconjunto de M colores con la distancia media más alta entre los colores, dada alguna función de distancia d .

Dicho de otra manera, considerando el conjunto inicial de N colores como un gráfico grande, no dirigido en el que están conectados todos los colores, desea encontrar el camino más largo que visita cualquier nodo M.

La solución de los problemas de gráficos completos de NP va más allá de mí, me temo, pero podrías intentar ejecutar una simple simulación física:

1. Genera M puntos aleatorios en el espacio de color
2. Calcule la distancia entre cada punto
3. Calcula los vectores de repulsión para cada punto que lo alejará de todos los otros puntos (usando 1 / ( distancia ^ 2) como la magnitud del vector)
4. Suma los vectores de repulsión para cada punto
5. Actualice la posición de cada punto según los vectores de repulsión sumados
6. Restringe las coordenadas fuera de límite (como la luminosidad negativa o por encima de una)
7. Repita desde el paso 2 hasta que los puntos se estabilicen
8. Para cada punto, seleccione el color más cercano al conjunto original de N

Está lejos de ser eficiente, pero para M pequeña puede ser lo suficientemente eficiente y dará resultados casi óptimos.

Si su función de distancia de color es simple, puede haber una forma más determinística de generar el subconjunto óptimo.

Answer 7

1. Comience con dos listas. CandidateColors, que inicialmente contiene sus distintos colores y SortedColors, que inicialmente está vacío.
2. Elija cualquier color y elimínelo de CandidateColors y colóquelo en SortedColors. Este es el primer color y será el más común, por lo que es un buen lugar para elegir un color que combine bien con su aplicación.
3. Para cada color en CandidateColors, calcule su distancia total. La distancia total es la suma de la distancia desde CandidateColor a cada uno de los colores en SortedColors.
4. Elimine el color con la distancia total más grande de CandidateColors y agréguelo al final de SortedColors.
5. Si CandidateColors no está vacío, regrese al paso 3.

Este codicioso algoritmo debería darte buenos resultados.

Answer 8

Puede ordenar los colores candidatos basándose en la distancia máxima de la distancia mínima a cualquiera de los colores de índice.

Usando distancia de color euclidiana:

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

Aunque puedes reemplazarlo con cualquier cosa que quieras. Solo necesita una rutina de distancia de color.

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 9

Esto también me suena a algún tipo de gráfico de resistencia donde tratas de trazar el camino de menor resistencia. Si invierte los requisitos, la ruta de resistencia máxima, tal vez podría usarse para producir un conjunto que desde el principio produce la diferencia máxima a medida que avanza, y hacia el final comienza a volver a valores más cercanos a los demás.

Por ejemplo, aquí hay una forma de quizás hacer lo que quieras.

1. Calcule la distancia (ref la otra publicación ) de cada color a todos los demás colores
2. Sume las distancias para cada color, esto le da una indicación de qué tan lejos está este color del resto de los colores en total
3. Ordene la lista por distancia, bajando

Aparentemente, esto produciría una lista que comienza con el color que está más alejado de todos los demás colores, y luego baja, los colores hacia el final de la lista estarían más cerca de otros colores en general.

Editar: Leer tu respuesta a mi primera publicación, sobre la subdivisión espacial, no encajaría exactamente con la descripción anterior, ya que los colores cercanos a otros colores caerían al final de la lista, pero digamos que tienes un grupo de colores en alguna parte, en al menos uno de los colores de ese grupo se ubicaría cerca del inicio de la lista, y sería el que generalmente estaba más alejado de todos los demás colores en total. Si eso tiene sentido.