Сортировка списка цветов в одном измерении?

Question

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

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

Например, сортировка по RGB работает не очень хорошо, так как она будет сортироваться в следующем порядке, например:

(1) R = 254 G = 0 B = 0 (2) R = 254 G = 255 B = 0 (3) R = 255 G = 0 B = 0 (4) R = 255 G = 255 B = 0

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

Но сортировка по HLS, вообще говоря, работает намного лучше, и я думаю, что HSL даже лучше; с любым из них красные будут рядом друг с другом, а желтые будут рядом друг с другом.

Но у HLS / HSL тоже есть некоторые проблемы; вещи, которые люди воспринимают как «черные», могут быть отделены друг от друга, как и вещи, которые люди воспринимают как «белые».

Опять же, я понимаю, что я в значительной степени должен признать, что будут некоторые подобные расколы; Мне просто интересно, нашел ли кто-нибудь лучший способ, чем HLS / HSL. И я знаю, что «лучше» несколько произвольно; Я имею в виду «более естественный для типичного человека».

Например, смутная мысль, которую я имел, но еще не пробовал, - возможно, «L - это самая важная вещь, если она очень высокая или очень низкая», но в остальном это наименее важно. Кто-нибудь пробовал это? Это сработало хорошо? Что конкретно вы решили "очень низкий" и "очень высокий" означает? И так далее. Или кто-нибудь нашел что-нибудь еще, что улучшило бы HSL?

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

Заранее спасибо за любую помощь.

Answer 1

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

Я наткнулся на 4 алгоритма сортировки цветов по яркости и сравнил их. Вот результат.

Я генерировал цвета в цикле, где использовался только каждый 400-й цвет. Каждый цвет представлен 2x2 пикселя, цвета сортируются от самых темных к самым светлым (слева направо, сверху вниз).

1-е изображение - Яркость (относительная)

0.2126 * R + 0.7152 * G + 0.0722 * B

2-е изображение - http://www.w3.org/TR/AERT#color-contrast

0.299 * R + 0.587 * G + 0.114 * B

3-е изображение - Модель цвета HSP

sqrt(0.299 * R^2 + 0.587 * G^2 + 0.114 * B^2)

4td изображение - WCAG 2.0 SC 1.4.3 относительная яркость и коэффициент контрастности формула

Рисунок иногда можно увидеть на 1-м и 2-м изображении в зависимости от количества цветов в одном ряду. Я никогда не замечал никаких паттернов на картинке из 3-го или 4-го алгоритма.

Если бы мне пришлось выбирать, я бы пошел с алгоритмом № 3, так как его гораздо проще реализовать и он примерно на 33% быстрее, чем 4-й

Answer 2

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

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

Более простой альтернативой (которая не будет работать идеально) будет выбор двух цветов «конечной точки», предпочтительно на противоположных сторонах цветового круга. Так, например, вы можете выбрать красный в качестве одного цвета конечной точки и синий в качестве другого. Затем вы должны преобразовать каждую точку данных о цвете в значение по шкале от 0 до 1, где очень красноватый цвет получит оценку около 0, а сильно голубоватый - около 1. Оценка. 5 указывает на цвет, в котором либо нет красного или синего цвета (он же зеленый), либо в равных количествах красный и синий (он же фиолетовый). Этот подход не идеален, но это лучшее, что вы можете сделать с этой проблемой.

Answer 3

Существует несколько стандартных методов сведения нескольких измерений к одному измерению с некоторым понятием «близости».

Я думаю, вам следует, в частности, проверить преобразование z-порядка .

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

Следующий Java-код должен помочь вам начать:

    public static int zValue(int r, int g, int b) {
            return split(r) + (split(g)<<1) + (split(b)<<2);
    }

    public static int split(int a) {
            // split out the lowest 10 bits to lowest 30 bits
            a=(a|(a<<12))&00014000377;
            a=(a|(a<<8)) &00014170017;
            a=(a|(a<<4)) &00303030303;
            a=(a|(a<<2)) &01111111111;
            return a;
    }

Answer 4

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

Я предполагаю, что вам нужно что-то простое и быстрое, которое выглядит «достаточно красиво» (пытаясь определить «оптимальный» вид эстетической окраски), поэтому вам достаточно простого подхода.

Я бы сказал, что HSL - это путь.Что-то вроде

sortValue = L * 5 + S * 2 + H

, предполагая, что H, S и L находятся в диапазоне [0, 1].

Answer 5

 A. R=254 G=0 B=0
 B. R=254 G=255 B=0
 C. R=255 G=0 B=0
 D. R=255 G=255 B=0

Вам нужно посмотреть на разницу между соседними цветами.

Разница между A и B равна 0 + 255 + 0 = 255. Разница между A и C равна 1 + 0 +.0 = 1.

Разница между A и B больше, чем A и C, поэтому A ближе к C, поэтому поменяйте местами B и C.

 A. R=254 G=0 B=0 
 C. R=255 G=0 B=0
 B. R=254 G=255 B=0
 D. R=255 G=255 B=0

Разница между C и B равна1 + 255 + 0 = 256. Разница между C и D равна 0 + 255 + 0 = 255.

Разница между C и B больше, чем C и D, поэтому C ближе к D, поэтому поменяйте местами Bи D.

A. R=254 G=0 B=0 
C. R=255 G=0 B=0
D. R=255 G=255 B=0
B. R=254 G=255 B=0

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

Также ...

Вам понадобится какой-нибудь забавный способ сравнения по вашему предмету.

Answer 6

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

Определите функцию расстояния в пространстве цветов, d(x, y) (где вводы x иy - это цвета, а на выходе возможно число с плавающей запятой).Функция расстояния, которую вы выбираете, может быть не очень важной.Скажем, это может быть сумма квадратов различий в компонентах R, G и B, или это может быть многочлен от различий в компонентах H, L и S (с компонентами, взвешенными по-разному в зависимости от того, насколько важно, по их мнению, ониare).

Затем вы вычисляете «расстояние» каждого цвета в вашем списке друг от друга, что фактически дает вам график.Далее вы рассчитываете минимальное остовное дерево вашего графа.Затем вы определяете самый длинный путь (без возврата), который существует в вашем MST.Конечные точки этого пути будут конечными точками окончательного списка.Затем вы пытаетесь «сплющить» дерево в линию, перенося точки в «ветвях» с вашего пути на сам путь.

Хмм.Это может не сработать, если ваш MST окажется в форме почти-петли в цветовом пространстве.Но, возможно, любой подход будет иметь эту проблему.