Продолжение: «Сортировка» цветов по отличимости

Question

Оригинальный вопрос

Если вам дано N максимально удаленных цветов (и некоторая связанная метрика расстояния), можете ли вы придумать способ сортировки этих цветов по некоторому порядку, так что первые M также достаточно близки к тому, чтобы быть максимально отличным набором?

Другими словами, учитывая кучу разных цветов, придумайте порядок, чтобы я мог использовать столько цветов, сколько мне нужно, начиная с самого начала, и быть уверенным, что все они различны и что соседние цвета также очень различны (например, голубовато-красный не рядом с красновато-синим).

Рандомизация в порядке, но определенно не оптимальна.

Пояснение: учитывая некоторый большой и визуально различимый набор цветов (скажем, 256 или 1024), я хочу отсортировать их так, чтобы при использовании первых, скажем, 16 из них, я получал относительно визуально различимый подмножество цветов. Это примерно эквивалентно тому, что я хочу отсортировать этот список из 1024 так, чтобы чем ближе отдельные цвета находились визуально, тем дальше они находились в списке.

Answer 1

N максимально удаленных цветов можно считать набором хорошо распределенных точек в 3-мерном (цветовом) пространстве. Если вы можете сгенерировать их из последовательности Halton , то любой префикс (первые M цветов) также состоит из хорошо распределенных точек.

Answer 2

Кажется, восприятие важно для вас, в этом случае вы можете рассмотреть возможность работы с воспринимаемым цветовым пространством, таким как YUV, YCbCr или Lab. Каждый раз, когда я их использовал, они давали мне гораздо лучшие результаты, чем один sRGB.

Преобразование в и из sRGB может быть затруднительным, но в вашем случае это может на самом деле упростить алгоритм и в качестве бонуса он в основном будет работать и для цветных жалюзи!

Answer 3

Эта проблема называется квантованием цвета и имеет много хорошо известных алгоритмов: http://en.wikipedia.org/wiki/Color_quantization Я знаю людей, которые реализовали подход октри с хорошим эффектом.

Answer 4

Это также звучит для меня как некий график сопротивления , где вы пытаетесь наметить путь наименьшего сопротивления. Если вы измените требования, путь максимального сопротивления, возможно, его можно использовать для создания набора, который с самого начала создает максимальную разницу по мере движения, а к концу начинает возвращаться к значениям, более близким к другим.

Например, вот один из способов сделать то, что вы хотите.

1. Рассчитайте расстояние (ref ваш другой пост ) от каждого цвета до всех остальных цветов
2. Суммируйте расстояния для каждого цвета, это дает вам указание для , как далеко этот цвет от всех других цветов в общей сложности
3. Упорядочить список по расстоянию, спускаясь

Кажется, что это приведет к созданию списка, который начинается с цвета, который находится дальше всего от всех других цветов, а затем идет вниз, цвета к концу списка будут ближе к другим цветам в целом.

Редактировать: чтение вашего ответа на мой первый пост о пространственном подразделении не совсем соответствует описанному выше описанию, так как цвета, близкие к другим цветам, окажутся внизу списка, но допустим, у вас есть группа цветов где-то, по крайней мере, один из цветов из этого кластера будет расположен ближе к началу списка, и это будет тот, который, как правило, самый дальний от всех других цветов в целом. Если это имеет смысл.

Answer 5

Вы можете просто отсортировать подходящие цвета на основе максимально удаленного от минимального расстояния до любого из индексных цветов.

Использование евклидова цветового расстояния:

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

Хотя вы можете заменить его на что угодно. Это просто требует рутины цветового расстояния.

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 6

1. Начните с двух списков. CandidateColors, который изначально содержит ваши отдельные цвета, и SortedColors, который изначально пуст.
2. Выберите любой цвет, удалите его из CandidateColors и поместите в SortedColors. Это первый цвет, который будет наиболее распространенным, поэтому это хорошее место, чтобы выбрать цвет, который хорошо сочетается с вашим приложением.
3. Для каждого цвета в CandidateColors рассчитайте его общее расстояние. Общее расстояние - это сумма расстояния от CandidateColor до каждого из цветов в SortedColors.
4. Удалите цвет с наибольшим общим расстоянием от CandidateColors и добавьте его в конец SortedColors.
5. Если CandidateColors не пусто, вернитесь к шагу 3.

Этот жадный алгоритм должен дать вам хорошие результаты.

Answer 7

Если я правильно понимаю вопрос, вы хотите получить подмножество M цветов с наибольшим средним расстоянием между цветами, учитывая некоторую функцию расстояния d .

Другими словами, рассматривая начальный набор N цветов как большой неориентированный граф, в котором все цвета связаны, вы хотите найти самый длинный путь , который посещает любой M узлов.

Я боюсь, что решение проблем с NP-полными графами намного превосходит меня, но вы можете попробовать запустить простое физическое моделирование:

1. Создать M случайных точек в цветовом пространстве
2. Рассчитать расстояние между каждой точкой
3. Рассчитать векторы отталкивания для каждой точки, которая отодвинет ее от всех других точек (используя 1 / ( distance ^ 2) в качестве величины вектора)
4. Суммируйте векторы отталкивания для каждой точки
5. Обновить положение каждой точки в соответствии с суммированными векторами отталкивания
6. Ограничить любые несвязанные координаты (например, светимость становится отрицательной или выше единицы)
7. Повторите с шага 2, пока точки не стабилизируются
8. Для каждой точки выберите ближайший цвет из исходного набора N

Это далеко не эффективно, но для небольших M оно может быть достаточно эффективным и даст почти оптимальные результаты.

Если ваша функция цветового расстояния проста, возможно, существует более детерминированный способ генерации оптимального подмножества.

Answer 8

Вы можете разделить их на формат RGB HEX, чтобы можно было сравнить R с R другого цвета, то же самое с G и B.

В том же формате, что и 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

Таким образом, единственное, что вам нужно будет решить, - это насколько близко вы хотите, чтобы цвета и какая приемлемая разница для сегментов считалась другой.

Answer 9

Вы имеете в виду, что из набора из N цветов вам нужно выбрать M цветов, где M лучшее представление N цветов в пространстве M?

В качестве лучшего примера уменьшите истинный цвет (24-разрядное цветовое пространство) до 8-разрядного отображенного цветового пространства (GIF?).

Для этого существуют алгоритмы квантования, например алгоритм Adaptive Spatial Subdivision , используемый ImageMagic.

Эти алгоритмы обычно не просто выбирают существующие цвета из исходного пространства, но и создают новые цвета в целевом пространстве, которые наиболее близко напоминают исходные цвета. В качестве упрощенного примера, если у вас есть 3 цвета в исходном изображении, где два цвета - красные (с различной интенсивностью или голубоватыми оттенками и т. Д.), А третий - синий, и необходимо уменьшить до двух цветов, целевое изображение может иметь красный цвет это какое-то среднее от исходного двух красных + синий цвет от исходного изображения.

Если вам нужно что-то еще, тогда я не понял вашего вопроса:)