Квантизация — уменьшение цветов изображения (wiki). Конечно, сейчас мало кому это необходимо, но задача сама по себе интересная.
Квантизированная Лена привлекает внимание
Например, старый добрый формат GIF использует палитру, максимум на 256 цветов. Если вы захотите сохранить серию своих селфи как gif-анимацию (кому бы это надо было), то первое, что вам, а точнее программе, которую вы будете для этого использовать, надо будет сделать – создать палитру. Можно использовать статическую палитру, например web-safe colors, алгоритм квантизации получиться очень простым и быстрым, но результат будет «не очень». Можно создать оптимальную палитру на основе цветов изображения, что даст результат наиболее визуально похожий на оригинал.
Алгоритмов создания оптимальной палитры несколько, каждый имеет свои плюсы и минусы. Я не стану утруждать читателя нудной теорией и формулами, во первых мне лень, во вторых большинству это не интересно – статью просто пролистают, рассматривая картинки.
Далее вас ждёт скучное и непонятное повествование о методе медианного сечения, алгоритму рассеивания ошибок (шума квантизации) по Флойду-Стейнбергу (и не только), особенностях цветового восприятия человеческого глаза, а так же немного говнокода.
Итак – метод медианного сечения. Он прост до безобразия. Первым делом надо из всех уникальных цветов изображения составить RGB куб. Далее рассечь его по самой длинной стороне. Например, диапазон красного у нас от 7 до 231 (длина 231-7=224), зелёного от 32 до 170 (длина 170-32=138), синего от 12 до 250 (длина 250-12=238), значит, будем «резать» куб по синей стороне. Получившиеся сегменты так же рассекаем по длинной стороне и т.д. пока не получим 256 сегментов. Для каждого сегмента высчитать средний цвет – так мы и получим палитру.
Что здесь можно улучшить? Первое, что приходит в голову – вычислять средний цвет не тупо сложив все цвета и разделив на их количество [ sum(color) / count(color) ], а с учётом, сколько раз каждый цвет встречается в изображении. То есть каждый цвет умножаем на количество его вхождений в изображении, полученные значения складываем, результат делим на количество вхождений в изображении всех цветов данного сегмента [ sum(color * total) / sum(total) ]. В результате, наиболее часто встречаемые цвета имеют приоритет при вычислении, но и редкие цвета вносят свои корректировки, поэтому палитра получается лучше, визуальное отклонение цветов меньше. Для лучших результатов желательно ещё учитывать гамму, но я оставил это на потом. Второе не так явно – медианное сечение совсем не учитывает особенности восприятия цвета человеческим глазом. Оттенки зелёного мы воспринимаем гораздо лучше оттенков синего. Я решил исправить это недоразумение и «сплющил» куб – длины сторон помножил на коэффициенты из этой статьи. В результате по зелёной и красной стороне сечений стало больше, по синей меньше. Такого решения я больше нигде не встречал (может плохо искал), но результат на лицо.
Теперь у нас есть оптимальная палитра, не идеальная конечно (я знаю, что её можно ещё улучшить), но достаточно хорошая. Следующий шаг – индексирование цветов изображения. Самый простой вариант – в каком сегменте находится цвет, такой и индекс. Быстро и просто. Но есть одно но, и даже не одно, поэтому к данному шагу мы ещё вернёмся.
Есть ещё один способ улучшить качество получаемого изображения – рассеивание ошибок. Тут тоже всё довольно просто – из индексируемого цвета вычитаем соответствующий цвет палитры, получаем ошибку, рассеиваем её по соседним пикселям в соответствии с определённой формулой (шаблоном), самая известная формула Флойда-Стейнберга, её я и использовал. При рассеивании ошибок размываются резкие переходы между цветами, и визуально кажется, что изображение содержит больше оттенков (цветов). Если интересно – про рассеивание ошибок подробно и интересно можно почитать тут. Этот алгоритм я так же решил допилить, помножив ошибку на всё те же коэффициенты, как оказалось, это была очень хорошая идея – так как сечений по синему диапазону стало меньше, в нём получалась значительная ошибка, и без корректировки ошибки коэффициентами рассеивание вносило много «шума».
Вот теперь можно снова вернуться к индексированию. Рассеиванием ошибок мы изменяем цвета пикселей и получаем такие, которых нет в нашем RGB-кубе (напомню, он составлен исключительно из цветов изображения). Теперь нельзя просто посмотреть в каком сегменте находится цвет, чтобы назначить индекс. Решение нашлось сразу – поиск ближайшего цвета в палитре. В данную формулу я подставил всё те же коэффициенты. Сравнивая результаты подбора цвета палитры по индексу сегмента в который входит исходный цвет и результаты поиска ближайшего цвета, наглядно увидел, что ближайший цвет часто оказывается в соседнем сегменте. Если исходный цвет находится ближе к центру сегмента – то индекс сегмента соответствует индексу цвета в палитре, но чем ближе исходный цвет к краям сегмента, тем больше вероятность, что ближайший цвет окажется в соседнем сегменте. В общем, единственный правильный путь индексирования – поиск ближайшего цвета в палитре. Но у поиска есть минус – он медленный, очень медленный. Писать числодробилку на python плохая идея.
Ну вот, хотел объяснить в двух словах, а получилась целая куча непонятной писанины. Надеюсь, код я пишу лучше, чем объясняю, поэтому вот ссылочка на github. Код несколько раз переписывался, сначала совершенствовался алгоритм, пока результат меня не устроил, потом оказалось, что он жрёт слишком много оперативы при обработке фотографий (сначала тестировал на небольших картинках), пришлось перенести RGB-куб, медианное сечение и карту пикселей в базу данных (sqlite). Скрипт работает очень медленно, но результат получается лучше, чем квантизация средствами PIL/Pillow и GIMP’ом (в нём эта операция называется индексирование).
Результат квантизации в GIMP, оптимальная палитра на 256 цветов + размывание цвета по Флойду-Стенбергу (нормальное)
Результат квантизации PIL/Pillow
image.convert(mode='P', dither=PIL.Image.FLOYDSTEINBERG, palette=PIL.Image.ADAPTIVE, colors=256)
Результат квантизации моим кодом
На что обратить внимание: рассеивание ошибки у GIMP сильно «шумит», PIL/Pillow создает не очень оптимальную палитру и практически не рассеивает ошибки (резкие переходы между цветами).
Если не видите разницу — посмотрите другие примеры на github.
P.S.: есть замечательная программа Color Quantizer, которая справляется с данной задачей лучше и быстрее, поэтому практического смысла мой скрипт не имеет, сделан исключительно из «спортивного» интереса.
Автор: Shrim
