Pull to refresh
506.21
Яндекс
Как мы делаем Яндекс

Почему непросто показать все цвета в одномерном пространстве, и сколько раз это можно сделать

Reading time 7 min
Views 41K
Яндекс умеет подсказывать цвета по их названию и находить близкие к ним. Некоторое время назад эту подсказку (внутри себя мы называем такие штуки «колдунщиками») пришлось переделывать, чтобы она соответствовала виду поисковых результатов после их редизайна. И мы воспользовались этим поводом, чтобы поработать над ним всерьёз, — ведь оказалось, что расположить цвета линейно — очень нетривиальная задача.







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




Колдунщик цветов появился в результатах поиска Яндекса в 2008 году. Когда его задумывали, нам хотелось, чтобы он стал не только игрушкой, которая откроет человеку цвет бедра испуганной нимфы, но и поможет узнать цвет по формуле, узнать нотацию по цвету, перевести код из одного цветового пространства в другое. Старая версия колдунщика состояла из барабана, колорпикера, инпута и 234 именованных цветов.

old colors


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

Быстро стало понятно, что на стандартных элементах его собрать не получится. Кроме того, колдунщик, нарисованный для старой страницы результатов поиска, не вписался бы в новую версию, да и делать трёхмерный барабан, по мнению наших дизайнеров, уже не модно. Так родился плоский дизайн. Главное, что хотелось поддержать в новой версии и чего не было раньше, — это просмотр кастомных цветов, которые не имели названия. В старой версии колдунщик отвечал на все запросы ближайшими именованными цветами и мог ввести людей в заблуждение. Теперь любой цвет можно увидеть в окружении ближайших именованных соседей или в другой яркости.



Главный дизайнер поиска 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.

CIELAB


После того как мы выбрали пространство цветов, мы можем дальше выбрать самую естественную, самую простую функцию качества решения — это сумма квадратов между соседними цветами расстановки. Оптимизация этой функции приводит к наиболее гладким переходам между соседними цветами (если применять CIE ΔE), и такое решение используется теперь в обновлённом колдунщике цветов. Однако оно специально не учитывает, что может быть лучше расположить группу соседних цветов подряд, чем использовать её часть, плавно перейти к другим оттенкам и вернуться к первым ещё раз. Кроме того, может быть желательно переходить от цвета к цвету «в одном направлении»: чтобы после тёмно-красного за чуть более светлым красным шёл ещё более светлый, а не более тёмный оттенок. Чтобы учесть эти пожелания, участники прибавляли к простой функции качества сумму квадратов разностей до более отдалённых соседей, или до усреднённого цвета всех ближайших соседей. Это улучшало вид расстановки в целом, но к сожалению, часто чрезмерно ухудшало вид вблизи — тот набор из пяти цветов, который колдунщик показывает за раз.

После выбора функции качества нужно решить, как её оптимизировать. Если эта функция выглядит как сумма квадратов разностей между стоящими рядом цветами, задача её оптимизации практически эквивалентна задаче оптимизации пути коммивояжёра (TSP), посещающего все места по одному разу и стремящегося максимально сократить суммарный путь. TSP является NP-сложной, но хорошо изученной проблемой, для приближённого решения которой в общественном доступе имеется несколько превосходных решателей — прежде всего LKH и Concorde. Использование специализированного решателя позволяет получить решение ближе к оптимальному и быстрее, чем это возможно с применением универсальных методов оптимизации.

TSP


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


Вариант сортировки с использованием TSP по метрике CIE94 от Zubchick

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






Несколько вариантов сортировки методом отжига от AOrazaev

Если бы это был не метод отжига, а метод градиентного спуска, он бы всегда переходил от решения с худшим качеством к решению с лучшим качеством. Но такой метод приводит к локальным оптимумам, когда каким-то простым преобразованием улучшить решение нельзя, но если всё в корне поменять, можно прийти к лучшему результату. Поэтому метод отжига иногда ухудшает решение. За счет этого возможно избавиться от локальных оптимумов в поиске глобального оптимума. Решения были неплохими, но недостаточно хорошие вблизи.

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


Попытка улучшить генетическим алгоритмом модифицированный TSP в метрике CIE1994 от XtremAlRaven

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

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

На самом деле, задача казалась сложной, потому что до того, как был объявлен конкурс, у разработчиков колдунщика в течение полутора месяцев оставался открытым вопрос, как хорошо расположить цвета. Они в итоге сами нашли хорошее решение, сравнимое по качеству с теми, которые участвовали потом в конкурсе. Кроме того, если заранее не знать некоторые элементы теории цвета, сложно понять, как решить эту задачу хорошо. Моё решение было готово на третий день конкурса, большинство других — в первую неделю.


Итоговая сортировка

Тут уже сложность возникла у команды, которая занималась колдунщиком, — им нужно было выбрать одно из почти сорока.
Tags:
Hubs:
+65
Comments 31
Comments Comments 31

Articles

Information

Website
www.ya.ru
Registered
Founded
Employees
over 10,000 employees
Location
Россия
Representative