В этом посте я хочу рассказать, какую интересную алгоритмическую задачу, которая потребовала погружения в теорию цвета, нам пришлось решать почти всем Яндексом, чтобы сделать новый колдунщик таким, каким его задумала команда.
Колдунщик цветов появился в результатах поиска Яндекса в 2008 году. Когда его задумывали, нам хотелось, чтобы он стал не только игрушкой, которая откроет человеку цвет бедра испуганной нимфы, но и поможет узнать цвет по формуле, узнать нотацию по цвету, перевести код из одного цветового пространства в другое. Старая версия колдунщика состояла из барабана, колорпикера, инпута и 234 именованных цветов.
Поначалу казалось, что возродить его на обновленной выдаче можно за пару недель. Первой частью этой задачи было привести внешний вид колдунщика к новому стилю страницы результатов поиска.
Быстро стало понятно, что на стандартных элементах его собрать не получится. Кроме того, колдунщик, нарисованный для старой страницы результатов поиска, не вписался бы в новую версию, да и делать трёхмерный барабан, по мнению наших дизайнеров, уже не модно. Так родился плоский дизайн. Главное, что хотелось поддержать в новой версии и чего не было раньше, — это просмотр кастомных цветов, которые не имели названия. В старой версии колдунщик отвечал на все запросы ближайшими именованными цветами и мог ввести людей в заблуждение. Теперь любой цвет можно увидеть в окружении ближайших именованных соседей или в другой яркости.
Главный дизайнер поиска kovchiy подарил команде файл с тысячами именованных цветов из личного архива. В итоге у нас было 1010 цветов, названия и координаты которых частично закреплены в стандартных списках цветов (таких как HTML Color Names, X11 Color Names), а частично — придуманы самостоятельно. И когда стали думать, как уложить их в колдунщик, началось самое сложное. Команда, которая работала над ним, решила даже устроить конкурс на лучшую сортировку цветов во внутренней соцсети Яндекса. Именно там я узнал о задаче и предложил своё решение, которое в итоге попало в продакшн. Но обо всем по порядку.
Итак, задача заключалась в том, чтобы упорядочить набор цветов на барабане (на линии или кольце) так, чтобы:
- переходы между соседними цветами были гладкими, а возможно, и менее контрастными — чтобы рядом стоящие цвета были похожими;
- близкие цвета были сгруппированы, чтобы похожие цвета стояли рядом.
Так выглядел исходный набор цветов без заданного порядка
Но уже эти два критерия являются:
- избыточными — группировка близких цветов повышает контрастность, а уменьшение контрастности разделяет группы;
- недостаточными — они допускают множество различных решений, при равенстве которых по данным критериям некоторые выделяются среди прочих менее определёнными качествами вроде лучшей видимой осмысленности расположения в целом;
- неопределёнными — они указывают, на что должно быть похоже желаемое решение, но не позволяют различить, какое из хороших решений лучше.
В итоге и судьи, и участники при сопоставлении решений больше полагались на вкус, чем на соответствие критериям.
Вручную, без помощи алгоритмов, не получится не только найти красивый порядок даже меньшего числа цветов, но и улучшить кем-то найденный. Если кажется, что некоторому цвету самое место в другой части барабана, то, переставив, обнаруживаешь резкий контраст: восприятие цвета зависит от фона, и новые соседи перемещённого цвета, казавшиеся на фоне близлежащих цветов столь на него похожими, после перемещения вдруг обнаруживают разительно иной оттенок.
Если подбирать расстановку цветов алгоритмически, естественно увидеть в проблеме задачу оптимизации и первым шагом к её решению выбрать цель оптимизации — функцию, которая сообщает, насколько хороша или плоха та или иная расстановка цветов.
Для построения этой функции необходима вспомогательная, называемая ?E, которая задаёт числом разность или степень похожести между двумя цветами. То есть если и только если разность одной пары близких цветов равна разности другой пары, наблюдателю должно казаться, что цвета в каждой из пар одинаково отстоят друг от друга. ?E составляет одну из фундаментальных проблем науки о цвете, но в определённых рамках она является вполне решённой. К счастью, функция разности между цветами давно исследуется в науке о цвете, и сейчас, где это необходимо, используются формула, опубликованная международной комиссией по освещению вместе с цветовым пространством CIE L*a*b* (LAB) в 1976 (в котором разность между цветами просто евклидово расстояние между ними) под названием CIE ?E и уточнённая в 1994 и 2000 годах. Участники конкурса, не знавшие о CIE ?E, обычно определяли ?E сами как евклидово расстояние в RGB и HSV.
Используя ?E, мы можем построить функцию оценки качества расположения цветов на барабане как сумму квадратов разностей между соседними цветами на барабане. Решение между участниками начинает различаться как раз с выбора функции качества решения. Все хорошие решения использовали CIE ?E; между собой они отличаются выбором функции качества решения и алгоритма её оптимизации.
Почему CIE ?E несколько, чем они отличаются по смыслу? Цветовое пространство CIE LAB было создано для того, чтобы цвета располагались равномерно. Оно отделяет яркость от двух других координат цвета, которые выбирает так, чтобы изменение цвета на несколько единиц яркости воспринималось как разница при изменении других координат на столько же единиц. Но и математическая простота функций, выражающих преобразование физического пространства (CIE XYZ) в LAB, по-видимому, имела существенное значение. Последующие эксперименты показали, что воспринимаемая цветовая разница не вполне, хоть и очень близко, сответствует заложенной в LAB. То есть LAB не является вполне однородным. Но найденные поправки к CIE ?E 1976 нельзя включить в новое цветовое пространство — то есть невозможно пространство, в котором исправленная CIE ?E была бы евклидовым расстоянием, как старая CIE ?E в CIE LAB. Поэтому до сих пор используется CIE LAB 1967.
После того как мы выбрали пространство цветов, мы можем дальше выбрать самую естественную, самую простую функцию качества решения — это сумма квадратов между соседними цветами расстановки. Оптимизация этой функции приводит к наиболее гладким переходам между соседними цветами (если применять CIE ?E), и такое решение используется теперь в обновлённом колдунщике цветов. Однако оно специально не учитывает, что может быть лучше расположить группу соседних цветов подряд, чем использовать её часть, плавно перейти к другим оттенкам и вернуться к первым ещё раз. Кроме того, может быть желательно переходить от цвета к цвету «в одном направлении»: чтобы после тёмно-красного за чуть более светлым красным шёл ещё более светлый, а не более тёмный оттенок. Чтобы учесть эти пожелания, участники прибавляли к простой функции качества сумму квадратов разностей до более отдалённых соседей, или до усреднённого цвета всех ближайших соседей. Это улучшало вид расстановки в целом, но к сожалению, часто чрезмерно ухудшало вид вблизи — тот набор из пяти цветов, который колдунщик показывает за раз.
После выбора функции качества нужно решить, как её оптимизировать. Если эта функция выглядит как сумма квадратов разностей между стоящими рядом цветами, задача её оптимизации практически эквивалентна задаче оптимизации пути коммивояжёра (TSP), посещающего все места по одному разу и стремящегося максимально сократить суммарный путь. TSP является NP-сложной, но хорошо изученной проблемой, для приближённого решения которой в общественном доступе имеется несколько превосходных решателей — прежде всего LKH и Concorde. Использование специализированного решателя позволяет получить решение ближе к оптимальному и быстрее, чем это возможно с применением универсальных методов оптимизации.
Такие универсальные методы требуются, если выбрана более сложная функция качества расстановки, учитывающая разность не только между ближайшими соседями.
Вариант сортировки с использованием TSP по метрике CIE94 от Zubchick
Два участника использовали метод отжига. Этот метод последовательной оптимизации решения. Сначала мы берем какое-то произвольное решение и затем стараемся постепенно его улучшать. На каждом шаге мы выбираем некоторое простое преобразование предыдущего решения. Например, переставить местами пару случайных цветов или соседних цветов, или перевернуть отрезок цветов, или поставить его в другом месте. После такой перестановки по функции качества решений сравнивается качество предыдущего и следующего решения.
Несколько вариантов сортировки методом отжига от AOrazaev
Если бы это был не метод отжига, а метод градиентного спуска, он бы всегда переходил от решения с худшим качеством к решению с лучшим качеством. Но такой метод приводит к локальным оптимумам, когда каким-то простым преобразованием улучшить решение нельзя, но если всё в корне поменять, можно прийти к лучшему результату. Поэтому метод отжига иногда ухудшает решение. За счет этого возможно избавиться от локальных оптимумов в поиске глобального оптимума. Решения были неплохими, но недостаточно хорошие вблизи.
Двое других наших коллег использовали генетические алгоритмы и либо не дождались хорошего результата, либо использовали неудачную функцию качества. Не считая версии XtremAlRaven, где за исходную точку было взято независимо полученное решение TSP, но которое не удалось заметно улучшить.
Попытка улучшить генетическим алгоритмом модифицированный TSP в метрике CIE1994 от XtremAlRaven
До сих пор я говорил о том, что результат можно получить только алгоритмически, но кроме выбора конкретного алгоритма было возможно некоторое ручное вмешательство. Во-первых, некоторые участники пытались сначала сгруппировать цвета вокруг нескольких выбранных точек (скажем, вокруг черного, красного, зеленого) и оптимизировать по отдельности все зоны, а потом их склеивать.
Я пробовал размещать цвета по вручную подобранным группам (так, чтобы похожие насыщенные цвета не смешивались между собой), находил граничные цвета, чтобы они плавно переходили друг в друга, и сортировал каждую группу между граничными цветами. Такой метод позволяет найти решение, которое лучше смотрится издали, потому что получается меньше одинаковых цветовых пятен в разных местах, но в колдунщике, когда будет показано только 5 цветов, оно выглядит немного хуже.
На самом деле, задача казалась сложной, потому что до того, как был объявлен конкурс, у разработчиков колдунщика в течение полутора месяцев оставался открытым вопрос, как хорошо расположить цвета. Они в итоге сами нашли хорошее решение, сравнимое по качеству с теми, которые участвовали потом в конкурсе. Кроме того, если заранее не знать некоторые элементы теории цвета, сложно понять, как решить эту задачу хорошо. Моё решение было готово на третий день конкурса, большинство других — в первую неделю.
Итоговая сортировка
Тут уже сложность возникла у команды, которая занималась колдунщиком, — им нужно было выбрать одно из почти сорока.
Комментарии (31)
Killy
23.07.2015 18:12+1Интересный доклад A Better Default Colormap for Matplotlib | SciPy 2015.
Используются более новые результаты по цветовым пространствам.
dom1n1k
24.07.2015 00:47Не совсем понятно, как там используются «новые результаты»? Докладчик мельком упомянул CIECAM02 (всё остальное вполне старое), но каким боком она к дефолтному градиенту для визуализации — я не понял.
Sap_ru
23.07.2015 18:14+7А «логичность» получившегося пространства с точки зрения пользователя не рассматривали? А зря.
Итоговая сортировка на взгляд человека не логична на средний интервалах — не знаешь куда крутить.
А вот последние два варианта полученные отжигом как раз выглядят очень логичными — есть закономерность на всех масштабах и можно предположить, где находится нужный цвет относительного текущего.
andreymironov
23.07.2015 19:21+2Неплохая попытка. А мы тупо используем self-avoiding walk по RGB-кубу, и все цвета при этом получаются максимально близкими друг к другу и с использованные строго один раз.
mib
23.07.2015 19:49+3Еще есть коэффициенты чувствительности человеческих глаз к RGB
R: 299
G: 587
B: 114
По идее, для вычисления «расстояния» между цветами — нужно учитывать восприятие цвета, а не абсолютную величину RGB.
Расстояние между R1,G1,B1 и R2,G2,B2 будет примерно такое: SQR ( ((R1-R2)*299)^2 + ((G1-G2)*587)^2 + ((G1-G2)*114)^2 )
Попробуйте с этим пересчитать шкалу, может будет красивее, как знать.stepik777
23.07.2015 20:20+2Вы статью читали? Там как раз написан правильный способ считать расстояние между цветами — перевести в пространство Lab и считать евклидово расстояние.
orivej Автор
23.07.2015 21:56+5Эти коэффициенты используются при рассчёте освещённости цвета по формуле Y = kRR + kGG + kBB (где Y является Y-координатой в пространстве XYZ), однако здесь R, G и B берутся в пространстве linear RGB, а не экранном. Кроме того, приведённые коэффициенты (0.30, 0.59, 0.11) задают пространство NTSC RGB, используемое в американском телевещании; в пространстве комьютерных экранов по умолчанию, sRGB, они равны (0.21, 0.72, 0.07). Впрочем, итоговая вормула воспринимаемой освещённости в очень грубом приближении похожа на L = k(kRr3 + kGg3 + kBb3)?, и было бы интересно найти коэффициенты, дающие в «наивной» формуле L = kRr + kGg + kBb наименьшую погрешность.
Если правильно воспользоваться этой формулой (по сути — рассчитать координату L в пространстве LAB), можно сравнивать освещённости цветов как |L1-L2|. Но если сравнивать все три координаты по приведённой вами формуле, результат будет неожиданный: (587 (G1-G2))2 + (114 (B1-B2))2 = 344569 (G1-G2)2 + 12996 (B1-B2)2: влияние зелёного будет настолько значительно, что различие в синем практически не будет учитываться.
На эту тему хорошо написал Bruce Lindbloom.
цитатаPerhaps you've learned that you can compute the luminance of an RGB color by taking 30% of its red component plus 59% of its green component plus 11% of its blue component. These weightings are often expressed in three-digit precision as 29.9% red, 58.7% green and 11.4% blue. Did you ever wonder where these weightings came from?
You can find them in the above table as the relative Y values for red, green and blue for the NTSC color model. The more precise weightings are 29.8839% red, 58.6811% green and 11.4350% blue. But it should also be obvious that the real RGB weightings depend upon the color system in use. So the «standard» weightings are incorrect for other RGB systems like sRGB or Adobe RGB (1998).
Another relevant fact is that these weightings must be made in a linear RGB space, that is, after the gamma companding function has been removed. It is very common to see the weightings applied bluntly to the companded RGB values, which is wrong.dom1n1k
24.07.2015 00:04+1Вообще те коэффициенты из так называемых рекомендаций 601 для телевидения. В более новых рекомендациях 709 и 2020 коэффициенты уже несколько другие.
И всё же luminance (Y) на русский переводят как «яркость», не «освещённость» (несмотря на потенциальную путаницу с brightness). Lightness (которая в CIE Lab) — «светлота». Освещенность это совершенно другой термин.
Коэффициенты можно применять и в линейных, и гамма-корректированных координатах — во втором случае получится Y', которая называется luma (адекватного перевода на русский, кажется, вообще нет).
SVlad
23.07.2015 20:59+1А почему цвета нужно было располагать по одной координате, если новы колдунщик — двухмерный?
orivej Автор
23.07.2015 22:55+2Расположение на плоскости не проще, чем на линии (если специально не подбирать цвета, хорошо лежащие на плоскости, отказываясь при этом от части уже имеющегося словаря цветов). И как использовать вторую координату? Считать обе координаты равнозначными и располагать в форме, близкой к квадрату? Тогда перемещение в обоих направлениях будет частично непредсказуемым. Располагать в форме вытянутого прямоугольника? Много цветов будет на границе, без соседей, и, если располагать по степени близости, пропадёт возможность быстро перейти к далёкому, но связанному с данным цвету. И как показывать цвет по неименованному запросу вроде #ABC000? В одномерном расположении его можно просто вставить между двумя именованными, а в двумерном — заменить им один из именованных? Так может не найтись какой-либо значимый цвет, например, по запросу #FF0001 — потеряется красный.
SVlad
23.07.2015 23:50+5Сам колдунщик очевидно использует координату L (светлота, от чёрного до белого) в качестве горизонтали. Ну и зациклить по тону, повышая с каждым оборотом насыщенность.
Цветовое пространство примерно так выглядит:
Acubed
24.07.2015 08:53Вот здесь можно покрутить такую модель.
SVlad
24.07.2015 09:09+1Ну это стандартный способ выбора цвета.
Вот хоть в GIMP, например:
По кругу тон, в центре — срез треугольника светлота-цветность по выбранному вектору тона.
Sirion
24.07.2015 09:05Плюсую предыдущего оратора. Вынести lightness в отдельную координату — и размерность задачи уменьшится на единицу, что положительно скажется не только на сложности решения, но и на юзабилити.
Nakilon
07.08.2015 01:07В «итоговой сортировке» есть три больших «зеленых» кластера и еще больше «синих». Возможно, при использовании двух измерений дробление было бы меньшим.
Не могли бы вы приложить список цветов, чтобы я, если найду время, тоже попробовал посортировать? В статье что-то списка не найду.
kns
24.07.2015 11:45Спасибо, что поиск по hex-представлению, обидно было, когда yandex.ru/yandsearch?text=%23adfaff сломалось.
P. S.
> Так родился плоский дизайн.
Приготовлен.
Отдельный.
Котел.
ivatsy
24.07.2015 13:30+1Большинство воспринимает RGB как некий абсолют цифрового определения цвета. Мало кто чётко определяет какой именно RGB он имеет ввиду, а их много: sRGB, AdobeRGB и десяток других. Сайт Яндекса не исключение.Та же ситуация с CMYK: не могут разные печатные машины, печатающие на огромном ассортименте бумаг, дать один и тот же цвет на те же значения CMYK.
В большинстве случаев с RGB проблем не возникает, так как sRGB используется практически везде. Но можно найти десятки вопросов на форумах почему Фотошоп «меняет цвет» в файле, или почему пипетка показывает разный цвет, где всё идентично.
Да и если вы думаете что Ваш монитор практически соответствует sRGB (то есть показывает «правильно»), я Вас огорчу, типичные мониторы имеют довольно большой разброс характеристик: от 55 до 110% охвата sRGB. Говорю это после калибровки не одной сотни мониторов.
Stalker_RED
24.07.2015 14:47Кстати о калибровке. Нет ли у вас под рукой ссылочки на какой-нибудь ликбез типа «калибровка для чайников при помощи гвоздя и пластиковой бутылки»?
ivatsy
24.07.2015 14:57Ручной калибровкой больше шансов сделать хуже чем лучше. Программа калибровки при помощи спектрометра возиться с монитором около часа, делая при этом множество измерений и расчётов.
dmagin
25.07.2015 21:39Используя ?E, мы можем построить функцию оценки качества расположения цветов на барабане как сумму квадратов разностей между соседними цветами на барабане.
На мой взгляд это вовсе не очевидное утверждение. Я так понимаю, что сумма квадратов разностей расстояний между соседями может быть минимальной, но при этом похожие цвета будут находиться в разных концах линейки.
И надо уточнить метрические свойства линейки. Являются ли начальная и конечная точки соседями?
Можно предложить альтернативные функции качества. Например, потребовать, чтобы линейные расстояния между цветами были максимально близки к их реальным (модельным, евклидовым). Тогда минимизировать надо сумму квадратов отклонения линейного расстояния от модельного. Такая сумма и будет функцией качества.
k06a
28.07.2015 12:33-3Ничего, что в природе все цвета и так разложены по одной оси? По частоте источника света. Надо лишь поднять формулы по физике Hz -> RGB. Или я чего-то не понимаю? И рядом будут похожие цвета, да.
Shekeen
03.08.2015 14:12Так вы опишете только монохромные цвета. Посмотрите здесь ru.wikipedia.org/wiki/Цветовая_модель на хроматическую диаграмму, эти цвета будут на ее ободке, там даже длины волн указаны соответствующие.
k06a
03.08.2015 15:33-1В каком смысле монохромную? Кто там втихую минусует меня? Пишите в лицо! Я вот о чем говорю: ru.wikipedia.org/wiki/%D0%92%D0%BE%D0%BB%D0%BD%D0%BE%D0%B2%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%81%D0%B2%D0%B5%D1%82%D0%B0
roman_kashitsyn
03.08.2015 15:53Реальные цвета состоят из пучка волн различных частот. Ваше предложение сработает разве что для описания цвета лазера.
Shekeen
03.08.2015 15:53Вы все-таки не посмотрели на цветовую диаграмму. Цвет, который вы видите, не обязательно получен одной волной.
macik_spb
28.07.2015 23:39+1Интересная статья и захватывающие картинки.
Вот я только понять не могу, неужели так много людей которые ищу какой-нибудь «пурпурно-фиолетовый»? Да еще при этом хотят получить точное воспроизведение цвета… Тем более что «стандартных названий», как написали выше, всего пара сотен. А уж их перевод на русский может быть не столь однозначен.
а частично — придуманы самостоятельно
А это-то, вообще, на каком основании включено в список? Просто потому что было?
Лично мне, в реальной жизни, гораздо чаще приходится искать цвета из палитры RAL или PANTONE. И я бы с большей радостью видел в выдаче их, нежели какой-нибудь «серобуромалиновый».
Есть, конечно, нюанс — и RAL и PANTONE это системы описания цветов, которые мы видим в реальной жизни, и перевести их однозначно в цветовое пространство мониторов не получится. Но, думаю, тут такая задача и не стоит, учитывая дешевые и не калиброванные мониторы большинства «юзеров».
Тем не менее предлагаю подумать над предложением.
Пусть это будет не в виде колдунщика с палитрой (как сейчас для означенных 1010 цветов). Достаточно просто вывод цвета:
p.s. Всем рекомендую отличный сайт colorscheme.ru. Там можно найти и упоминаемые RAL и PANTONE, и многое другое.
kaichou
В самой первой картинке из пяти плашек точно не зашифровано гипнотическое послание?