k-means и pixel-art

 У меня на практике давно встала нехитрая задача перевода картинки в ограниченное количество цветов, по сути — пиксель-арт на минималках. Нужно это в нескольких случаях:

• Изображение сильно большое и тратить время пиксель-артиста — очень дорого, да и мало кто возьмётся.
• На изображении немного чётких деталей, так что тратить на него ценное время художника не стоит.

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

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

Чтобы протестировать эту идею, я взял условный k-means из scikit (sklearn) Питона и попробовал сделать через него — т. е. пиксель по умолчанию имеет тот цвет, что и центр кластера, в который попадает. Но здесь я немного сделал пару хаков - во-первых, цвета взял в HSV, чтобы не кластеризовать условные красные, зелёные и синие цвета, а скорее исходить из оттенка, а во-вторых, добавил мультипликаторы для исходных значений, которые должны давать потенциальное улучшение результата.

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

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

В заключение небольшой пример:

Исходное изображение

Результат (32 базовых цвета, альфа сохранена, т.к. важное)

Не идеально, но в принципе ок.