Квантизация изображений

    Квантизация — уменьшение цветов изображения (wiki). Конечно, сейчас мало кому это необходимо, но задача сама по себе интересная.


    Квантизированная Лена привлекает внимание

    Например, старый добрый формат GIF использует палитру, максимум на 256 цветов. Если вы захотите сохранить серию своих селфи как gif-анимацию (кому бы это надо было), то первое, что вам, а точнее программе, которую вы будете для этого использовать, надо будет сделать – создать палитру. Можно использовать статическую палитру, например web-safe colors, алгоритм квантизации получиться очень простым и быстрым, но результат будет «не очень». Можно создать оптимальную палитру на основе цветов изображения, что даст результат наиболее визуально похожий на оригинал.

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

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

    Предыстория
    Давным-давно, когда Nokia была тёплой и ламповой главенствовала на рынке смартфонов, а владельцы смартфонов гордо звали себя «смартфонщики», в те стародавние времена писал я простенькие программки на python для series60. На одну из них намедни наткнулся копаясь в архивах. GifTool – программка для создания gif-анимации из набора картинок. В ней я реализовал квантизацию методом медианного сечения, алгоритм сжатия LZW, вся структура файла создавалась самостоятельно, для неизменившихся на следующем слайде пикселей использовалась прозрачность, чтобы уменьшить итоговый размер файла. Захотелось мне освежить свою память, посмотреть – как же она работала. Открыл код и … Это чувство, когда ты не можешь разобраться в своём говнокоде десятилетней давности. Про PEP8 я тогда не знал, поэтому читаемость кода была чуть менее чем никакой (тогда мне нравился минимализм, как и многим начинающим программистам). Прослезился, поплевался, отрефакторил в PyCharm, разобрался как реализовал метод медианного сечения, по быстрому накидал «грязный» скрипт. Работает! Палитра создаётся, изображение на выходе получается сносное. И тут меня закусило – смогу ли я добиться лучших результатов, чтобы картинка визуально была как можно ближе к оригиналу.

    Итак – метод медианного сечения. Он прост до безобразия. Первым делом надо из всех уникальных цветов изображения составить 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, которая справляется с данной задачей лучше и быстрее, поэтому практического смысла мой скрипт не имеет, сделан исключительно из «спортивного» интереса.
    UPD: обновил проект на github. Добавил алгоритм квантизации Octree (октодерево), популярные формулы рассеивания ошибок, поиск ближайшего цвета по среднему значению красного.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 28

      0
      На жёлтом пухе появились блики, кромка крыла стала зелёной, палитрой это объяснить сложно, это явные искажения цветов, поскольку и синий и жёлтый в палитре остался.
      Вообще говоря. расстояния между цветами в кубе — это не расстояния между цветами, а не пойми что, надо на это обратить внимание.
        0
        Искажения цвета объясняются приоритетом зелёного канала при сечении. Там где блики — пух на оригинальном изображении самый светлый, GIMP и PIL это просто проигнорировали, затемнив данные участки. Край крыла на оригинале светло-голубой, из-за приоритета зелёного канала оттенков синего в палитре меньше, поэтому ближайшим к светло-голубому оказался свело-зелёный, GIMP и PIL сделали этот участок серым.
        При усечении 300 000 цветов до 256 искажения в любом случае будут, главное — постараться сделать их наименее заметными.
        По поводу расстояния между цветами в кубе — именно поэтому я и использовал коэффициенты, чтобы при вычислении расстояния учитывать относительную яркость цвета. Медианное сечение позволяет разделить куб на сегменты содержащие равное количество цветов, я при сечении учёл относительную яркость. Так же относительная яркость учитывается при поиске ближайшего цвета и рассеивании ошибок. А вот вычисление «среднего» цвета сегмента реализовано не лучшим образом. По хорошему надо ещё учитывать гамму.
          +1
          Скажите, а вы пробовали разбивать не куб RGB, а HSL?
            0
            Или CMYK-гиперкуб.
              0
              Не пробовал, но в планах было, а так же разобраться с гаммой. Пока занят другим проектом.
          +1
          результат на лицо

          Всегда нравились подобные двусмысленности в статьях. Всегда интересно, специально автор фразу подбирал, или случайно вышло.
          P.S. Это не про орфографию.
            +3
            Изначально хотел повториться «палитра получается лучше, визуальное отклонение цветов меньше», но мне показалось, что повторов в статье итак много, исправил на первое, что пришло в голову.
            Хотя, посмотрите на лицо Лены, разве не результат? Можете на github сравнить с тем, что с ней сделали GIMP и PIL.
            А вообще, мне статья не нравиться целиком и полностью, не удалось мне правильно изложить свои мысли, но я не уверен, что смогу переписать её лучше.
            0
            Ограничение в 256 цветов в GIF — это миф
              0
              Да, это не секрет. Мне было интересно именно создание оптимальной палитры, об этом и статья. Я мог бы сохранить картинки как png8, но посчитал, что в gif нагляднее.
              0
              Сколько искал, так и не смог найти программу, способную привести изображение к необходимому набору цветов, при условии, что палитра шире 256 значений (нужно было разложить на ~430 цветов).

              Может кто подскажет что-нибудь подходящее?
                0
                Color Quantizer позволяет задать произвольное количество цветов.
                  0
                  Большое спасибо!

                  Пробные прогоны вызвали массу положительных эмоций. Жаль, раньше не знал о такой полезной утилите.
                    0
                    А вы, я так понимаю, её автор.
                      0
                      Да. Если есть какие-то вопросы, буду рад помочь.
                  0
                  Одно время хотел написать про это статью, но руки так и не дошли.

                  ИМХО, метод медианного среза нагляднее показывать не на RGB-кубе, а на массиве пикселей в изображении (R,G,B,A,R,G,B,A...). Сортируем массив по наибольшему range (не знаю, как по-русски сказать) цветового канала, делим массив пополам и проделываем то же самое в половинках, пока количество массивов не станет равно количеству необходимых цветов, усредняем значение цвета в каждом куске и возвращаем пиксели на место.

                  А метод на деревьях квадрантов даёт меньше искажений и имеет больше простора для оптимизации.
                    0
                    Посмотрите код, именно так и реализовано. Просто представить RGB-куб проще, поэтому обычно его в пример и приводят.
                    Как я сказал в предыстории, это проект выходного дня. Теперь охота разобраться с octree и k-средних, так что, может статья будет иметь продолжение.
                      0
                      Не, я как раз не про сам алгоритм говорю, а его представление. Лично мне RGB куб не кажется наглядным.
                    0

                    Честно говоря, мне результат Гимпа нравится больше всего. Особенно заметно на большом ярком соцветии в центре — у вашего алгоритма есть заметная постеризация.

                      0

                      Посмотрел другие примеры. Ленну ваша программа обработала лучше. А вот на "пустыне" опять постеризация (появились горизонтальные полосы на небе около горизонта), в отличие от Гимпа.

                        0
                        Вы не путаете? Полосы у PIL, у моего результата полосы почти не заметны. У GIMP явно видно рассеивание ошибки, изображение получается в крапинку. Что скажите про Маяк? На нём все эти недостатки видны очень хорошо.
                          0

                          Точно не путаю. Да, у Гимпа шума намного больше. Но вопрос видимо в чуствительности разных людей к разным искажениям. Для меня шум гораздо меньше портит изображение чем полосы. Маяк у вас вышел лучше.

                          0
                          Сейчас подумалось: по Флойду-Стейнбергу рассеивание только по соседним пикселям, поэтому постеризация всё ещё заметна (без рассеивания ошибки она явная). Наверное формулы «Jarvis, Judice, and Ninke », «Stucki » и «Sierra-3» дали бы лучший результат, за счёт большего поля рассеивания.
                          0
                          Сохраните картинки и сравните их в полном размере. У GIMP результат очень шумный, при уменьшении это не так заметно (скорей всего на это и рассчитано).
                          0
                          Недавно решал такую задачу на JavaScript. Я правда применял кластеризацию K-Means (в задаче необходимо было найти небольше число основных оттенков), и преобразовывал в цветовое пространство Lab (это пространство специально создано для того, чтобы понимать на сколько отличаются цвета с точки зрения человеческого восприятия).
                            0

                            Жалко, что статья очень короткая. При таком многообещающем названии можно было рассказать побольше. Хотя бы про ту же формулу Флойда — Стейнберга побольше или про кластеризацию, скажем, методом k средних.

                              0
                              составить RGB куб. Далее рассечь его по самой длинной стороне

                              скорее всего имелся ввиду параллелограмм

                                0

                                Параллелепипед?

                                  0
                                  Прямоугольный…

                              Only users with full accounts can post comments. Log in, please.