Если вам даны N максимально удаленных друг от друга цветов (и некоторая связанная с ними метрика расстояния), можете ли вы придумать способ отсортировать эти цвета в определенном порядке, чтобы первые M были достаточно близки к тому, чтобы быть максимально отличным множеством?
Другими словами, если дана куча разных цветов, придумайте такой порядок, чтобы я мог использовать столько цветов, сколько мне нужно, начиная с самого начала, и быть уверенным, что все они разные и что соседние цвета тоже очень разные (например, голубовато-красный не будет соседствовать с красновато-синим).
Случайный выбор - это хорошо, но, конечно, не оптимально.
Уточнение: Учитывая некоторый большой и визуально различимый набор цветов (скажем, 256 или 1024), я хочу отсортировать их так, чтобы при использовании первых, скажем, 16 из них я получил относительно визуально различимое подмножество цветов. Это эквивалентно, примерно, тому, что я хочу отсортировать этот список из 1024 цветов так, чтобы чем ближе визуально отдельные цвета, тем дальше друг от друга они находились в списке.
Похоже, восприятие является важным для вас, в таком случае вы, возможно, захотите рассмотреть возможность работы с перцептивное цветовое пространство, например, YUV, YCbCr или лаборатории. Каждый раз, когда я'вэ использовал эти, они дали мне гораздо лучших результатов, чем в одиночку цветового пространства sRGB.
Преобразования цветового пространства sRGB может быть боль, но в вашем случае это действительно может сделать алгоритм проще и в качестве бонуса он будет в основном работать для цвета жалюзи!
Н максимально далеких цветов можно считать набор хорошо-распределенных точек в 3-мерном (цвет) пространства. Если вы можете создавать их из последовательность Халтон, то какой префикс (первые M цвета) также состоит из равномерно распределенных точек.
Это также похоже на своего рода график сопротивления, где вы пытаетесь наметить путь наименьшего сопротивления. Если инвертировать требования, путь максимального сопротивления, то это, возможно, можно использовать для получения набора, который с самого начала дает максимальную разницу по мере продвижения, а к концу начинает возвращаться к значениям, более близким к остальным.
Например, вот один из способов сделать то, что вы хотите.
Это, кажется, создаст список, который начинается с цвета, который находится дальше всего от всех других цветов, а затем идет вниз, цвета к концу списка будут ближе к другим цветам в целом.
Edit: Читая ваш ответ на мое первое сообщение, о пространственном подразделении, это не совсем подходит под вышеприведенное описание, так как цвета, близкие к другим цветам, упадут в низ списка, но, допустим, у вас есть кластер цветов где-то, по крайней мере, один из цветов из этого кластера будет расположен рядом с началом списка, и это будет тот цвет, который в целом наиболее удален от всех других цветов в целом. Если это имеет смысл.
Эта проблема называется Цвет квантования, и имеет много хорошо известных алгоритма: http://en.wikipedia.org/wiki/Color_quantization я знаю людей, которые реализовали подход восьмеричного дерева набора для хорошего эффекта.
Вы могли бы просто отсортировать цветов кандидата на основе максимального расстояния минимальной дистанции, чтобы любой из цветов.
Используя цвет Евклидово расстояние:
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;
}
}
}
}
Если я'м, что он правильно понял вопрос, вы хотите получить подмножество М цвета с самые высокие средние дистанции между цветами, учитывая некоторые функции расстояния д.
Иными словами, учитывая начальный набор Н цвета, как большие, неориентированный граф, в котором все цвета соединяются, вы хотите, чтобы найти длинный путь что посетить м узлы.
Решения NP-полных задач графика это далеко за пределы меня я'м боюсь, но вы могли бы попробовать запустить простое физическое моделирование:
Это'далеко от эффективного, но и для малого м это может быть достаточно эффективным, и он будет давать около оптимальных результатов.
Если на расстоянии цвет функция проста, может быть более детерминированным способом формирования оптимального подмножества.
Это жадный алгоритм должен дать вам хорошие результаты.
Вы можете разделить их в формате RGB HEX, чтобы можно было сравнить R с R's другого цвета, то же самое с 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
Таким образом, единственное, что вам нужно решить, это насколько близкими должны быть цвета и какова приемлемая разница, чтобы сегменты считались разными.
Вы имеете в виду, что из набора N цветов нужно выбрать M цветов, где M < N, таких, что M является лучшим представлением N цветов в пространстве M?
В качестве лучшего примера, уменьшите истинный цвет (24-битное цветовое пространство) до 8-битного отображенного цветового пространства (GIF?).
Для этого существуют алгоритмы квантования, например, алгоритм Adaptive Spatial Subdivision, используемый ImageMagic.
Эти алгоритмы обычно не просто выбирают существующие цвета из исходного пространства, а создают новые цвета в целевом пространстве, которые наиболее похожи на исходные. В качестве упрощенного примера, если у вас есть 3 цвета в исходном изображении, два из которых красные (с разной интенсивностью или голубоватыми оттенками и т.д.), а третий - синий, и вам нужно уменьшить изображение до двух цветов, целевое изображение может иметь красный цвет, который является неким средним значением двух красных + синий цвет из исходного изображения.
Если вам нужно что-то другое, тогда я не понял ваш вопрос :)