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

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

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

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

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

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

4.08.2008 15:14:47
9 ОТВЕТОВ

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

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

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

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

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

2
23.05.2017 12:34:21

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

2
12.08.2008 12:11:29

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

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

2
12.08.2008 12:33:29

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

2
25.08.2008 08:44:06

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

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

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

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

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

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

1
16.10.2008 17:11:04
Это не NP-полный. Это либо сортировка O (NLog (N)) по максимуму минимального расстояния до любых индексных цветов O (N), либо по среднему O (N). Это явно O (N + NLog (N)) или O (NLog (N)). В худшем случае вам нужно добавить отсортированные цвета к индексным цветам, сделав его N²Log (N). Найдите лучшее, добавьте его в список цветов индекса. Начать сначала.
Tatarize 3.09.2012 20:57:57
  1. Начните с двух списков. CandidateColors, который изначально содержит ваши отдельные цвета, и SortedColors, который изначально пуст.
  2. Выберите любой цвет и удалите его из CandidateColors и поместите в SortedColors. Это первый цвет, и он будет самым распространенным, так что это хорошее место, чтобы выбрать цвет, который хорошо сочетается с вашим приложением.
  3. Для каждого цвета в CandidateColors рассчитайте его общее расстояние. Общее расстояние - это сумма расстояния от CandidateColor до каждого из цветов в SortedColors.
  4. Удалите цвет с наибольшим общим расстоянием от CandidateColors и добавьте его в конец SortedColors.
  5. Если CandidateColors не пусто, вернитесь к шагу 3.

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

1
21.11.2008 09:29:38

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

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

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;
            }
        }
    }
}
1
3.09.2012 20:50:02
Хотя, на самом деле, это может выбрать два очень похожих цвета из кандидатов цвета. Возможно, вы захотите просто найти лучший кандидат цвет, добавить его к индексным цветам и начать все заново.
Tatarize 3.09.2012 21:01:04

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

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

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

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

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

0
4.08.2008 15:29:49

Вы можете разделить их на формат 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

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

0
4.08.2008 15:31:15