Если вам дается N максимально удаленных цветов (и некоторая связанная метрика расстояния), можете ли вы придумать способ сортировки этих цветов в некотором порядке, так чтобы первые M также были достаточно близки к тому, чтобы быть максимально отличным набором?
Другими словами, учитывая кучу разных цветов, придумайте порядок, чтобы я мог использовать столько цветов, сколько мне нужно, начиная с самого начала, и быть уверенным, что все они различны и что соседние цвета также очень различны (например, голубовато-красный не рядом с красновато-синим).
Рандомизация - это нормально, но, конечно, не оптимально.
Пояснение: учитывая некоторый большой и визуально различимый набор цветов (скажем, 256 или 1024), я хочу отсортировать их так, чтобы при использовании первых, скажем, 16 из них, я получал относительно визуально различимое подмножество цветов. Грубо говоря, это равносильно тому, что я хочу отсортировать этот список из 1024, так что чем ближе отдельные цвета визуально, тем дальше они находятся в списке.
Это также звучит как график сопротивления, где вы пытаетесь наметить путь наименьшего сопротивления. Если вы переверните требования, путь максимального сопротивления, возможно, его можно использовать для создания набора, который с самого начала создает максимальную разницу по мере вашего продвижения, и к концу начинает возвращаться к значениям, более близким к другим.
Например, вот один из способов сделать то, что вы хотите.
- Рассчитайте расстояние (см. Ваш другой пост ) от каждого цвета до всех других цветов
- Суммируйте расстояния для каждого цвета, это дает вам представление о том, как далеко этот цвет от всех других цветов в целом
- Упорядочить список по расстоянию, спускаясь вниз
Кажется, что это приведет к созданию списка, который начинается с цвета, который находится дальше всего от всех других цветов, а затем идет вниз, цвета к концу списка будут ближе к другим цветам в целом.
Редактировать: чтение вашего ответа на мой первый пост о пространственном подразделении не совсем соответствует описанному выше описанию, так как цвета, близкие к другим цветам, окажутся внизу списка, но, скажем, у вас есть кластер цветов где-то, в по крайней мере, один из цветов из этого кластера будет расположен ближе к началу списка, и это будет тот, который, как правило, наиболее далеко от всех других цветов в целом. Если это имеет смысл.
Эта проблема называется квантованием цвета и имеет много хорошо известных алгоритмов: http://en.wikipedia.org/wiki/Color_quanization. Я знаю людей, которые реализовали подход октри для получения хорошего эффекта.
Кажется, восприятие важно для вас, в этом случае вы можете рассмотреть возможность работы с воспринимаемым цветовым пространством, таким как YUV, YCbCr или Lab. Каждый раз, когда я их использовал, они давали мне гораздо лучшие результаты, чем один sRGB.
Преобразование в и из sRGB может быть трудной задачей, но в вашем случае это может на самом деле упростить алгоритм и в качестве бонуса он в основном будет работать и на дальтоники!
N максимально удаленных цветов можно считать набором хорошо распределенных точек в 3-мерном (цветовом) пространстве. Если вы можете сгенерировать их из последовательности Halton , то любой префикс (первые M цветов) также состоит из хорошо распределенных точек.
Если я правильно понимаю вопрос, вы хотите получить подмножество M цветов с наибольшим средним расстоянием между цветами, учитывая некоторую функцию расстояния d .
Другими словами, рассматривая начальный набор из N цветов как большой, неориентированный граф, в котором все цвета связаны, вы хотите найти самый длинный путь, который посещает любые M узлов.
Боюсь, что решение проблем с NP-полными графами намного превосходит меня, но вы можете попробовать запустить простое физическое моделирование:
- Генерация M случайных точек в цветовом пространстве
- Рассчитать расстояние между каждой точкой
- Рассчитайте векторы отталкивания для каждой точки, которая отодвинет ее от всех остальных точек (используя 1 / ( расстояние ^ 2) в качестве величины вектора)
- Суммируйте векторы отталкивания для каждой точки
- Обновите положение каждой точки в соответствии с суммированными векторами отталкивания.
- Ограничить любые координаты вне границы (например, светимость становится отрицательной или выше единицы)
- Повторите с шага 2, пока точки не стабилизируются
- Для каждой точки выберите ближайший цвет из исходного набора N
Это далеко не эффективно, но для малых M это может быть достаточно эффективно, и это даст почти оптимальные результаты.
Если ваша функция цветового расстояния проста, может быть более детерминированный способ генерации оптимального подмножества.
- Начните с двух списков. CandidateColors, который изначально содержит ваши отдельные цвета, и SortedColors, который изначально пуст.
- Выберите любой цвет и удалите его из CandidateColors и поместите в SortedColors. Это первый цвет, и он будет самым распространенным, так что это хорошее место, чтобы выбрать цвет, который хорошо сочетается с вашим приложением.
- Для каждого цвета в CandidateColors рассчитайте его общее расстояние. Общее расстояние - это сумма расстояния от CandidateColor до каждого из цветов в SortedColors.
- Удалите цвет с наибольшим общим расстоянием от CandidateColors и добавьте его в конец SortedColors.
- Если CandidateColors не пусто, вернитесь к шагу 3.
Этот жадный алгоритм должен дать вам хорошие результаты.
Вы можете просто отсортировать подходящие цвета на основе максимально удаленного от минимального расстояния до любого из индексных цветов.
Используя евклидово цветовое расстояние:
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;
}
}
}
}
Вы имеете в виду, что из набора из N цветов вам нужно выбрать M цветов, где M <N, так что M - лучшее представление N цветов в пространстве M?
В качестве лучшего примера, уменьшите истинный цвет (24-битное цветовое пространство) до 8-битового отображенного цветового пространства (GIF?).
Для этого существуют алгоритмы квантования, например алгоритм Adaptive Spatial Subdivision , используемый ImageMagic.
Эти алгоритмы обычно не просто выбирают существующие цвета из исходного пространства, но и создают новые цвета в целевом пространстве, которые наиболее близко напоминают исходные цвета. В качестве упрощенного примера, если у вас есть 3 цвета в исходном изображении, где два цвета - красные (с различной интенсивностью или голубоватыми оттенками и т. Д.), А третий - синий, и необходимо уменьшить до двух цветов, целевое изображение может иметь красный цвет это что-то среднее от исходного двух красных + синий цвет от исходного изображения.
Если вам нужно что-то еще, то я не понял вашего вопроса :)
Вы можете разделить их на формат 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
Таким образом, единственное, что вам нужно будет решить, - это насколько близко вы хотите, чтобы цвета и какая разница была приемлемой для сегментов, которые будут считаться разными.