Как мы с моими друзьями Гонсалесом и Вудсом делали схему для вышивки по Властелину Колец

Что может быть более рождественского, чем десятичасовая версия They taking the hobbits to Isengard Властелин Колец? Вот и моя супруга решила так же и заказала схему вышивки для карты Cредиземья.

Немного багета

Когда схема для вышивки пришла, и супруга начала вышивать, она попросила меня посмотреть, получится ли убрать автоматически некоторые пиксели, которые находятся в гордом одиночестве на расстоянии двух-трех пикселей от совпадающего по цвету. При этом соседствуют с очень похожими на них самих цветами.
За вечер я написал парсер, и мы загнали схему в питон. Выяснилось еще более прекрасное. Несмотря на то, что с тебя хотят звонкий шекель, работа идет по принципу «хуяк-хуяк и на etsy». Никакой пред- и постобработки изображения, чтобы убрать артефакты сжатия или слишком мелкие детали. А еще выяснилось, что некоторыми цветами надо вышить всего 12-20 пикселей на все изображение. Это при общем размере 500x375 и 8 метрах нитки в пачке.

После пары попыток переделать старую схему решили сделать свою с нуля.

Немного фотошопа

Открываем бесплатный онлайн-фотошоп photopea. @graynk тут подсказал его в треде про крутой софт. 10/10.
Сжимаем наше изображение до нужного размера и впадаем в тоску.

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

Убираем мелкие хер-пойми-зачем нужные детали. Их лучше вышить поверх готовой карты швом «назад иголку». Например, традиционно присутствующий на карте Великий Западный Тракт превращается в мешанину полутонов из-за своей маленькости. Да и вообще — лично мне бы больше хотелось видеть там путь братства, чем абстрактный тракт, который, конечно, важная артерия Средиземья, но мало участвует в истории.

Немного классического компьютер-вижна

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

Однако нам недостаточно просто выбрать для каждого пикселя ближайший тон из палитры ниток для вышивания. Это приведет нас к требованию скупить половину палитры, и от некоторых потратить по паре сантиметров из 8-метрового мотка. Мы хотим наперед задаться каким-то количеством цветов и не превышать его. А еще мы хотим, чтобы каждого цвета использовалось какое-то разумное количество. Пара пикселей на моток нас не устраивает.
Будем бинить по-умному. Нам хотелось бы выбрать то самое, наперед заданное, количество цветов так, чтобы они лучше всего подходили для описания конкретной картинки. Для этого нам понадобится дата сатанизм старый добрый K-means clustering. Никакого рокет-сайнса, мы берем k случайных пикселей картинки и назначаем их новыми опорными цветами. Теперь будем по кругу повторять вот что (все это в цветовом пространстве):

• Для каждого пикселя картинки найдем ближайший опорный цвет i. Теперь этот пиксель относится к i-тому кластеру.
• Для каждого кластера переместим его опорный цвет в его фактический центр. То есть в усредненный по кластеру цвет.
• Проверим, сильно ли переместились опорные цвета с прошлого раза. Если нет, считаем, что мы закончили.

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

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

Итак, мы нашли k новых опорных цветов. Пока они никак не связаны с нашей желаемой палитрой. Для начала просто притягиваем цвет к ближайшему существующему в палитре цветов производителя ниток. (Ставим скрапиться сайт по переводу этого дела в RGB и идем пить чай). Но этого на самом деле мало. У производителя всего 500 цветов. Нам хотелось бы иметь возможность получать более мягкие оттенки для равномерного фона. И вот тут кроется одна из подстав типичных автогенерированных вышивочных схем в интернете. По дефолту это достигается диттерингом (так-то и было сделано в купленной карте), но нам это не очень-то подходит.
Диттеринг — это алгоритм получения промежуточного цвета за счет комбинации пикселей двух цветов в разной пропорции.

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

Куда лучше заставить его смешать вместе цвета еще до того, как он продел нитку в иглу. Выясняем, во сколько ниток будет вышиваться наша картинка (скорее всего в две) и создаем все возможные комбинации с таким количеством цветов. Проблема в том, что если просто притягивать к ближайшему цвету в расширенном пространстве, то статистически все цвета окажутся смешанными (потому что все пары — это уже 124 750 вместо 500 чистых). Но это заставит нас поделить общее количество разных цветов пикселей пополам (мы же, на самом деле, задавались количеством разных ниток, которые покупаем, как мерой геморроя).
Пока лучшее, что я придумал — жадный подбор. На каждом шагу:

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

Оценку выигрыша и потерь я произвожу опять при помощи LAB-пространства. Я просто расстояние между истинной и побиненной картинкой до изменения и после. Если ошибка уменьшилась — этот набор опорных цветов лучше предыдущего, если ошибка увеличилась — хуже.
Проблема жадного алгоритма в том, что выбор локально оптимального решения на каждом шаге не гарантирует глобального оптимума (за исключением специальных случаев). Скорее всего, эту задачу подбора цветов можно поставить более аккуратно (линейное программирование, вероятно) и получать более хороший результат. Но это проблема для более лучшего меня. Потом.

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

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

Генерирование схемы

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

Результат

В целом, остался еще целый ряд нерешенных проблем. Мне не очень нравится жадный алгоритм, хотелось бы помогать выбирать нужные параметры умнее, чем поиск по сетке с предпросмотром, ко всему этому хотелось бы сделать нормальный интерфейс. Но уже сейчас за 4-5 минут и три команды можно получить схему для вышивки. И наслаждаться классикой.

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