Блог Яндекса Голосов: 7 Адрес блога: http://company.yandex.ru/blog/ Добавлен: 2007-12-13 21:24:18 блограйдером Luber

Колдунщик цветов: возвращение

2015-04-16 13:55:54 (читать в оригинале)

Если вы когда-нибудь задавались вопросом, какого цвета бедро испуганной нимфы, недоумевали, о каком таком «перванше» идёт речь в любимой книге, или хотели перекодировать нужный оттенок из RGB в HSV, вы уже наверняка знакомы с колдунщиком цветов Яндекса. Если нет, то вот он, просим любить и жаловать.


Колдунщик цветов появился в 2008 году. К нему быстро привыкли: кому-то он помогал в работе, кому-то просто нравилось вращать барабан и узнавать о существовании цветов вроде «бисмарк-фуриозо». Но летом прошлого года страница результатов поиска поменяла интерфейс, и некоторыми возможностями пришлось временно пожертвовать — в том числе и колдунщиком цветов. Зато вернулся он в улучшенном виде.

Старый колдунщик знал 234 цвета. В новом их стало 1010: мы взяли за основу несколько существующих списков именованных цветов (это те, за которыми закреплены конкретное название и координаты в стандартных цветовых моделях вроде RGB) и добавили несколько оттенков, названия для которых придумали сами. Теперь нужно было разложить эти цвета по порядку — чтобы людям было удобно пользоваться колдунщиком, переходы между соседними цветами должны быть плавными. Надо ли говорить, что это оказалось и сложнее, и интереснее, чем мы думали.

Так выглядел наш набор цветов до сортировки.


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

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

Такая физиология человеческого восприятия отражена в цветовой модели RGB. Это трёхмерное пространство, заданное осями, по которым увеличивается интенсивность красной (red), зеленой (green) и синей (blue) компонент. Поместить наши цвета в это пространство никакой проблемы не составляет — их координаты известны. Проблема — в плавности переходов от одного цвета к другому.


Чтобы переход был плавным, две соседние «бусины» должны минимально отличаться по цвету — для человеческого восприятия. Это уточнение не такое очевидное, каким кажется. Логично предположить, что чем меньше один цвет отстоит от другого в математической модели, тем меньше они отличаются на глаз. Значит, необходимо найти такое расположение для нашей нитки, чтобы между последовательными бусинами-цветами было наименьшее расстояние. Это верный ход мысли, но не для всякой цветовой модели.

Цветовые пространства большинства моделей, в том числе и RGB, не однородны для нашего восприятия. Другими словами, человеческим глазом один и тот же сдвиг по осям координат ощущается по-разному в разных цветовых регионах. Если взять два цвета — например, красный и тёмно-зеленый — и изменить их координаты так, чтобы сдвиг по всем трём осям был равным и параллельным, то на глаз разница между красным и получившимся тёмно-красным будет больше, чем между тёмно-зеленым и тёмно-тёмно-зеленым. Это значит, что если мы найдем математический алгоритм, который по оптимальному маршруту обойдёт все интересующие нас объекты такого цветового пространства и нанижет их на одномерную нитку, то для человеческого глаза изменение её окраса не будет равномерным — а мы-то хотели добиться именно этого.

Одна из моделей, в которых визуальная однородность достигается математическими средствами, назвается CIELAB — в ней-то мы и решали нашу задачу. По своему устройству CIELAB принципиально отличается от RGB: оси координат в ней задают яркость и две пары противоположных цветов (красный — зеленый, синий — жёлтый).


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

Тут напрашивается решение с помощью алгоритма «ближайшего соседа»: выбираем точку, которая к нам ближе всего, добравшись до неё, ищем новую ближайшую точку и так далее. Однако алгоритм «ближайшего соседа» решает только локальную задачу, игнорируя картину в целом. Представьте себе архипелаг, острова которого разбросаны так же неравномерно, как 1010 цветов в нашем пространстве. Если путешествовать по ним, каждый раз двигаясь к ближайшему острову, мы в результате рискуем очень скоро оказаться, например, на южном краю архипелага, оставив не охваченными еще десять островов на севере. Тогда нам придется совершить длинный перелет, или, в нашем случае, — резкий переход от одного цвета к другому. Так что это решение нам не подходит.

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


Теперь повторить путь коммивояжёра в цветовом пространстве CIELAB вы можете на странице результатов поиска. Просто поищите, например, [цвет Яндекса].