Followup: «Сортировка» цвета по различительной

голоса
18

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

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

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

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

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

Задан 04/08/2008 в 16:14
источник пользователем
На других языках...                            


9 ответов

голоса
2

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

Ответил 25/08/2008 в 09:44
источник пользователем

голоса
2

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

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

Ответил 12/08/2008 в 13:33
источник пользователем

голоса
2

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

Ответил 12/08/2008 в 13:11
источник пользователем

голоса
2

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

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

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

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

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

Ответил 04/08/2008 в 16:38
источник пользователем

голоса
1

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

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

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;
            }
        }
    }
}
Ответил 03/09/2012 в 21:50
источник пользователем

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

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

Ответил 21/11/2008 в 10:29
источник пользователем

голоса
1

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

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

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

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

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

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

Ответил 16/10/2008 в 18:11
источник пользователем

голоса
0

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

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

Ответил 04/08/2008 в 16:31
источник пользователем

голоса
0

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

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

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

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

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

Ответил 04/08/2008 в 16:29
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more